Talk is Cheap, Show Me the Code!

0%

松鼠的新家

Posted on In

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a_1，再去a_2，……，最后到a_n，去参观新家。

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

现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入描述:

第一行一个整数n，表示房间个数 2<=n<=300000;

第二行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

说明

有n个点的一棵树， 沿着a1~an顺序去访问每个点， 路径上经过的点都要被加上一次，最后输出每个点被加的次数。

songshuhome.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <vector>
using namespace std;

const int N = 300010;
const int S = 20;

int n;
int path[N];

vector<int>edges[N];

int dis[N], dep[N];
int fa[N][S+1];
int cnt[N];
void dfs(int x, int f, int d){
    fa[x][0] = f, dep[x] = dep[f] +1, dis[x] = d;
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i];
        if(y==f) continue;
        dfs(y, x, d + 1);
    }
}

void goUp(int &x, int step){
//  starts from 0
    for(int i=0;i<=S;i++){
        if(step & (1<<i)) x = fa[x][i];
    }
}

int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    goUp(x, dep[x]-dep[y]);
    if(x==y) return x; // easy to forget
    for(int i=S;i>=0;i--){
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y= fa[y][i];
    }
    return fa[x][0];
}

void DFS(int x, int f){
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i];
        if(y==f) continue;
        DFS(y, x);
        cnt[x] += cnt[y];
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &path[i]);
    int a, b;
    for(int i=1;i<n;i++){
        scanf("%d%d", &a, &b);
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1, 0, 0);
    for(int j=1;j<=S;j++)
        for(int i=1;i<=n;i++)
            fa[i][j] = fa[ fa[i][j-1] ][j-1];

//    for(int i=1;i<=n;i++) printf("%d ", fa[i][0]);
//    puts("");
    for(int i=1;i<n;i++){
        a = path[i], b = path[i+1];
        int c = lca(a, b);
//        printf("%d %d %d\n", a, b, c);
        cnt[a]++, cnt[b]++, cnt[c]--, cnt[fa[c][0]]--;
    }

    DFS(1, 0);
    for(int i=2;i<=n;i++) cnt[path[i]]--; //why?
    for(int i=1;i<=n;i++) printf("%d\n", cnt[i]);
    return 0;

}