首页 > 其他分享 >NC20139 [JLOI2014]松鼠的新家

NC20139 [JLOI2014]松鼠的新家

时间:2023-06-23 15:25:14浏览次数:52  
标签:JLOI2014 新家 fa int 房间 dep NC20139 松鼠 糖果

题目链接

题目

题目描述

松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在“树”上。

松鼠想邀请维尼小熊前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,……,最后到an,去参观新家。

可是这样会导致维尼重复走很多房间,懒惰的维尼不听地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。维尼是个馋家伙,立马就答应了。

现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间an是餐厅,餐厅里他准备了丰盛的大餐,所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入描述

第一行一个整数n,表示房间个数
第二行n个整数,依次描述a1-an
接下来n-1行,每行两个整数x,y,表示标号x和y的两个房间之间有树枝相连。

输出描述

一共n行,第i行输出标号为i的房间至少需要放多少个糖果,才能让维尼有糖果吃。

示例1

输入

5
1 4 5 3 2
1 2
2 4
2 3
4 5

输出

1
2
1
2
1

备注

对于全部的数据,\(2 \le n \le 3 \times 10^5,1 \le a_i \le n\) 。

题解

知识点:差分,LCA。

可以用树剖解决,但对于这种最后查询的问题,可以不那么麻烦,用树上差分就行。

我们对相邻两个点的路径做路径加 \(1\) ,可以差分配合LCA实现,最后用做一次树上前缀和即可。

注意,两次路径的端点相交处只需要走一次,因此我们我们对相交的点的答案减 \(1\) 即可。

时间复杂度 \(O(n \log n)\)

空间复杂度 \(O(n \log n)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 3e5 + 7;
int a[N];
vector<int> g[N];

int f[27][N], dep[N];
void dfs(int u, int fa) {
    f[0][u] = fa;
    dep[u] = dep[fa] + 1;
    for (int i = 1;i <= 20;i++) f[i][u] = f[i - 1][f[i - 1][u]];
    for (auto v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
}

int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20;i >= 0;i--) {
        if (dep[f[i][u]] >= dep[v]) u = f[i][u];
        if (u == v) return u;
    }
    for (int i = 20;i >= 0;i--) {
        if (f[i][u] != f[i][v]) {
            u = f[i][u];
            v = f[i][v];
        }
    }
    return f[0][u];
}

int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; }

int delta[N], add[N];
void calc(int u, int fa) {
    for (auto v : g[u]) {
        if (v == fa) continue;
        calc(v, u);
        delta[u] += delta[v];
    }
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n - 1;i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

    for (int i = 2;i <= n;i++) {
        int u = a[i - 1], v = a[i];
        int lca = LCA(u, v);
        delta[u]++;
        delta[v]++;
        delta[lca]--;
        delta[f[0][lca]]--;
    }
    calc(1, 0);
    for (int i = 2;i <= n;i++) delta[a[i]]--;
    for (int i = 1;i <= n;i++) cout << delta[i] << '\n';
    return 0;
}

标签:JLOI2014,新家,fa,int,房间,dep,NC20139,松鼠,糖果
From: https://www.cnblogs.com/BlankYang/p/17499185.html

相关文章

  • 【题解】[JLOI2014]镜面通道
    题目描述:在一个二维平面上,有一个镜面通道,由镜面\(AC,BD\)组成,\(AC,BD\)长度相等,且都平行于\(x\)轴,\(B\)位于\((0,0)\)。通道中有\(n\)个外表面为镜面的光学元件,光学元件\(\alpha\)为圆形,光学元件\(\beta\)为矩形(这些元件可以与其他元件和通道有交集,具体看下图)。......
  • 搬新家喽
    如题,网站如下Z呵呵的个人博客(zaughter.cn)经过了一周的忙碌,现在我的个人博客网站终于搭建成功了,以后我会在我的网站和博客园同步更新,希望大家能去捧个场。我的个人网站......
  • 【题解】P4632 [APIO2018] 新家
    码力底下,思维迟钝,我该怎么办?还是说这题太毒?题意给定一个\(n\)个商店,第\(i\)个商店的类型为\(t_i\),在\([a_i,b_i]\)时间营业,位于位置\(x_i\)。定义某一时刻一......