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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #include <bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
#define mod 998244353
#define MAXN 2e6
#define MS 300009
LL n,m;
LL a[MS];
vector<LL > vc[MS];
LL fa[MS],sz[MS],dep[MS],zson[MS];
LL tot,top[MS],dfn[MS],w[MS];
LL p[MS<<2];
LL la[MS<<2];
LL ac[MS];
void dfs1(LL x,LL f){
sz[x] = 1;
dep[x] = dep[f]+1;
fa[x] = f;
int maxzson = 0;
for(auto &i:vc[x]){
if(i != f){
dfs1(i,x);
sz[x] += sz[i];
if(sz[i] > maxzson){
maxzson = sz[i];
zson[x] = i;
}
}
}
}
void dfs2(LL x,LL tp){
dfn[x] = ++tot;
top[x] = tp;
w[x] = 0;
if(zson[x]) dfs2(zson[x],tp);
for(auto &i:vc[x]){
if(i != fa[x] && i != zson[x]){
dfs2(i,i);
}
}
}
void push_down(int rt){
if(la[rt]){
p[ls] += la[rt];
p[rs] += la[rt];
la[ls] += la[rt];
la[rs] += la[rt];
la[rt] = 0;
}
}
void update(int L,int R,int l,int r,int rt,LL val){
if(L <= l && r <= R){
p[rt] += val;
la[rt] += val;
return;
}
push_down(rt);
int m = l+r>>1;
if(m >= L) update(L,R,l,m,ls,val);
if(m < R) update(L,R,m+1,r,rs,val);
}
LL query(int pos,int l,int r,int rt){
if(l == r) return p[rt];
int m = l+r>>1;
push_down(rt);
if(m >= pos) return query(pos,l,m,ls);
else return query(pos,m+1,r,rs);
}
void op(LL x,LL y){
while(top[x] != top[y]){
if(dep[ top[x] ] < dep[ top[y] ]) swap(x,y);
update(dfn[top[x]],dfn[x],1,n,1,1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
update(dfn[x],dfn[y],1,n,1,1);
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=2;i<=n;i++){
LL u,v;
cin >> u >> v;
vc[u].push_back(v);
vc[v].push_back(u);
}
dfs1(1,1);
dfs2(1,1);
for(int i=2;i<=n;i++){
LL u = a[i-1];
LL v = a[i];
op(u,v);
update(dfn[v],dfn[v],1,n,1,-1);
}
for(int i=1;i<=n;i++){
LL ans = query(dfn[i],1,n,1);
cout << ans << "\n";
}
return 0;
}
|
