#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7;
vector<int>V[LIM];
int T[LIM], ile[LIM], wynik[LIM], odl[2][LIM], odw[LIM], wys[LIM], jaki[LIM], czy[LIM], aktile;
int trma[4*LIM], trmi[4*LIM], lazy[4*LIM], N=1;
vector<int>ojcowie;
void spl(int v) {
trma[2*v]+=lazy[v];
trma[2*v+1]+=lazy[v];
trmi[2*v]+=lazy[v];
trmi[2*v+1]+=lazy[v];
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
if(r<a || b<l) return;
if(a<=l && r<=b) {
trma[v]+=x;
trmi[v]+=x;
lazy[v]+=x;
return;
}
if(lazy[v]) spl(v);
int mid=(l+r)/2;
upd(2*v, l, mid, a, b, x);
upd(2*v+1, mid+1, r, a, b, x);
trma[v]=max(trma[2*v], trma[2*v+1]);
trmi[v]=min(trmi[2*v], trmi[2*v+1]);
}
int zejdzmi(int v, int l, int r) {
if(l==r) return l;
if(lazy[v]) spl(v);
int mid=(l+r)/2;
if(trmi[2*v]<=trmi[2*v+1]) return zejdzmi(2*v, l, mid);
return zejdzmi(2*v+1, mid+1, r);
}
int zejdzma(int v, int l, int r) {
if(l==r) return l;
if(lazy[v]) spl(v);
int mid=(l+r)/2;
if(trma[2*v]>=trma[2*v+1]) return zejdzma(2*v, l, mid);
return zejdzma(2*v+1, mid+1, r);
}
void dodaj(int x) {
if(odw[x] || !czy[x]) return;
odw[x]=1;
++ile[T[x]];
if(ile[T[x]]==1) ++aktile;
}
void usun(int x) {
if(!odw[x] || !czy[x]) return;
odw[x]=0;
--ile[T[x]];
if(ile[T[x]]==0) --aktile;
}
void schodz() {
while(trma[1]>0) {
int p=zejdzma(1, 0, N-1);
usun(ojcowie[p]);
upd(1, 0, N-1, p, p, -INF);
}
while(trmi[1]==-INF) {
int p=zejdzmi(1, 0, N-1);
dodaj(ojcowie[p]);
upd(1, 0, N-1, p, p, INF);
}
}
void DFS(int x, int o, int k) {
for(auto i : V[x]) if(i!=o) {
odl[k][i]=odl[k][x]+1;
DFS(i, x, k);
}
}
void DFS2(int x, int o) {
for(auto i : V[x]) if(i!=o) {
DFS2(i, x);
wys[x]=max(wys[x], wys[i]+1);
}
}
void DFS3(int x, int o, int k) {
ojcowie.pb(x);
upd(1, 0, N-1, odl[k][x]-wys[x], odl[k][x]-1, 1);
schodz();
if(jaki[x]==k) wynik[x]=aktile;
upd(1, 0, N-1, odl[k][x]-wys[x], odl[k][x]-1, -1);
czy[x]=1;
dodaj(x);
pair<int,int>ma={-1, -1};
for(auto i : V[x]) if(i!=o) {
if(wys[i]>=ma.st) {
ma.nd=ma.st;
ma.st=wys[i];
} else ma.nd=max(ma.nd, wys[i]);
}
for(auto i : V[x]) if(i!=o) {
int p=ma.st;
if(wys[i]==p) p=ma.nd;
upd(1, 0, N-1, odl[k][x]-p-1, odl[k][x]-1, 1);
DFS3(i, x, k);
upd(1, 0, N-1, odl[k][x]-p-1, odl[k][x]-1, -1);
}
usun(x);
czy[x]=0;
ojcowie.pop_back();
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
while(N<n) N*=2;
rep(i, n-1) {
int a, b;
cin >> a >> b; --a; --b;
V[a].pb(b);
V[b].pb(a);
}
rep(i, n) {
cin >> T[i]; --T[i];
}
DFS(0, 0, 0);
pair<int,int>ma={-1, -1};
rep(i, n) ma=max(ma, {odl[0][i], i});
int x=ma.nd;
odl[0][x]=0;
DFS(x, x, 0);
ma={-1, -1};
rep(i, n) ma=max(ma, {odl[0][i], i});
int y=ma.nd;
DFS(y, y, 1);
rep(i, n) if(odl[0][i]<odl[1][i]) jaki[i]=1;
rep(i, n) wys[i]=0;
DFS2(x, x);
DFS3(x, x, 0);
rep(i, n) wys[i]=0;
rep(i, 2*N) trma[i]=trmi[i]=lazy[i]=0;
rep(i, n) odw[i]=czy[i]=0;
rep(i, m) ile[i]=0;
aktile=0;
DFS2(y, y);
DFS3(y, y, 1);
rep(i, n) cout << wynik[i] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
11100 KB |
Output is correct |
2 |
Correct |
4 ms |
11164 KB |
Output is correct |
3 |
Correct |
4 ms |
11352 KB |
Output is correct |
4 |
Correct |
5 ms |
11352 KB |
Output is correct |
5 |
Correct |
5 ms |
11356 KB |
Output is correct |
6 |
Correct |
6 ms |
11356 KB |
Output is correct |
7 |
Correct |
6 ms |
11356 KB |
Output is correct |
8 |
Correct |
4 ms |
11356 KB |
Output is correct |
9 |
Correct |
5 ms |
11360 KB |
Output is correct |
10 |
Correct |
5 ms |
11356 KB |
Output is correct |
11 |
Correct |
5 ms |
11240 KB |
Output is correct |
12 |
Correct |
5 ms |
11356 KB |
Output is correct |
13 |
Correct |
7 ms |
11352 KB |
Output is correct |
14 |
Correct |
5 ms |
11356 KB |
Output is correct |
15 |
Correct |
5 ms |
11356 KB |
Output is correct |
16 |
Correct |
4 ms |
11356 KB |
Output is correct |
17 |
Correct |
5 ms |
11356 KB |
Output is correct |
18 |
Correct |
5 ms |
11356 KB |
Output is correct |
19 |
Correct |
5 ms |
11356 KB |
Output is correct |
20 |
Correct |
7 ms |
11356 KB |
Output is correct |
21 |
Correct |
6 ms |
11336 KB |
Output is correct |
22 |
Correct |
5 ms |
11356 KB |
Output is correct |
23 |
Correct |
5 ms |
11356 KB |
Output is correct |
24 |
Correct |
5 ms |
11356 KB |
Output is correct |
25 |
Correct |
5 ms |
11368 KB |
Output is correct |
26 |
Correct |
4 ms |
11352 KB |
Output is correct |
27 |
Correct |
6 ms |
11356 KB |
Output is correct |
28 |
Correct |
6 ms |
11356 KB |
Output is correct |
29 |
Correct |
6 ms |
11424 KB |
Output is correct |
30 |
Correct |
4 ms |
11356 KB |
Output is correct |
31 |
Correct |
6 ms |
11424 KB |
Output is correct |
32 |
Correct |
5 ms |
11356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
244 ms |
22100 KB |
Output is correct |
2 |
Correct |
412 ms |
33488 KB |
Output is correct |
3 |
Correct |
65 ms |
16724 KB |
Output is correct |
4 |
Correct |
494 ms |
29212 KB |
Output is correct |
5 |
Correct |
815 ms |
48580 KB |
Output is correct |
6 |
Correct |
673 ms |
38872 KB |
Output is correct |
7 |
Correct |
473 ms |
28956 KB |
Output is correct |
8 |
Correct |
508 ms |
31348 KB |
Output is correct |
9 |
Correct |
519 ms |
30392 KB |
Output is correct |
10 |
Correct |
528 ms |
30548 KB |
Output is correct |
11 |
Correct |
308 ms |
29888 KB |
Output is correct |
12 |
Correct |
756 ms |
41240 KB |
Output is correct |
13 |
Correct |
654 ms |
38664 KB |
Output is correct |
14 |
Correct |
733 ms |
38220 KB |
Output is correct |
15 |
Correct |
292 ms |
29712 KB |
Output is correct |
16 |
Correct |
687 ms |
42248 KB |
Output is correct |
17 |
Correct |
679 ms |
39300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
362 ms |
27216 KB |
Output is correct |
2 |
Correct |
795 ms |
49016 KB |
Output is correct |
3 |
Correct |
74 ms |
17244 KB |
Output is correct |
4 |
Correct |
498 ms |
29864 KB |
Output is correct |
5 |
Correct |
860 ms |
50472 KB |
Output is correct |
6 |
Correct |
695 ms |
39944 KB |
Output is correct |
7 |
Correct |
497 ms |
30036 KB |
Output is correct |
8 |
Correct |
596 ms |
34344 KB |
Output is correct |
9 |
Correct |
530 ms |
32888 KB |
Output is correct |
10 |
Correct |
545 ms |
31572 KB |
Output is correct |
11 |
Correct |
389 ms |
30284 KB |
Output is correct |
12 |
Correct |
871 ms |
46288 KB |
Output is correct |
13 |
Correct |
659 ms |
38732 KB |
Output is correct |
14 |
Correct |
786 ms |
38960 KB |
Output is correct |
15 |
Correct |
293 ms |
30660 KB |
Output is correct |
16 |
Correct |
661 ms |
43804 KB |
Output is correct |
17 |
Correct |
677 ms |
40344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
11100 KB |
Output is correct |
2 |
Correct |
4 ms |
11164 KB |
Output is correct |
3 |
Correct |
4 ms |
11352 KB |
Output is correct |
4 |
Correct |
5 ms |
11352 KB |
Output is correct |
5 |
Correct |
5 ms |
11356 KB |
Output is correct |
6 |
Correct |
6 ms |
11356 KB |
Output is correct |
7 |
Correct |
6 ms |
11356 KB |
Output is correct |
8 |
Correct |
4 ms |
11356 KB |
Output is correct |
9 |
Correct |
5 ms |
11360 KB |
Output is correct |
10 |
Correct |
5 ms |
11356 KB |
Output is correct |
11 |
Correct |
5 ms |
11240 KB |
Output is correct |
12 |
Correct |
5 ms |
11356 KB |
Output is correct |
13 |
Correct |
7 ms |
11352 KB |
Output is correct |
14 |
Correct |
5 ms |
11356 KB |
Output is correct |
15 |
Correct |
5 ms |
11356 KB |
Output is correct |
16 |
Correct |
4 ms |
11356 KB |
Output is correct |
17 |
Correct |
5 ms |
11356 KB |
Output is correct |
18 |
Correct |
5 ms |
11356 KB |
Output is correct |
19 |
Correct |
5 ms |
11356 KB |
Output is correct |
20 |
Correct |
7 ms |
11356 KB |
Output is correct |
21 |
Correct |
6 ms |
11336 KB |
Output is correct |
22 |
Correct |
5 ms |
11356 KB |
Output is correct |
23 |
Correct |
5 ms |
11356 KB |
Output is correct |
24 |
Correct |
5 ms |
11356 KB |
Output is correct |
25 |
Correct |
5 ms |
11368 KB |
Output is correct |
26 |
Correct |
4 ms |
11352 KB |
Output is correct |
27 |
Correct |
6 ms |
11356 KB |
Output is correct |
28 |
Correct |
6 ms |
11356 KB |
Output is correct |
29 |
Correct |
6 ms |
11424 KB |
Output is correct |
30 |
Correct |
4 ms |
11356 KB |
Output is correct |
31 |
Correct |
6 ms |
11424 KB |
Output is correct |
32 |
Correct |
5 ms |
11356 KB |
Output is correct |
33 |
Correct |
244 ms |
22100 KB |
Output is correct |
34 |
Correct |
412 ms |
33488 KB |
Output is correct |
35 |
Correct |
65 ms |
16724 KB |
Output is correct |
36 |
Correct |
494 ms |
29212 KB |
Output is correct |
37 |
Correct |
815 ms |
48580 KB |
Output is correct |
38 |
Correct |
673 ms |
38872 KB |
Output is correct |
39 |
Correct |
473 ms |
28956 KB |
Output is correct |
40 |
Correct |
508 ms |
31348 KB |
Output is correct |
41 |
Correct |
519 ms |
30392 KB |
Output is correct |
42 |
Correct |
528 ms |
30548 KB |
Output is correct |
43 |
Correct |
308 ms |
29888 KB |
Output is correct |
44 |
Correct |
756 ms |
41240 KB |
Output is correct |
45 |
Correct |
654 ms |
38664 KB |
Output is correct |
46 |
Correct |
733 ms |
38220 KB |
Output is correct |
47 |
Correct |
292 ms |
29712 KB |
Output is correct |
48 |
Correct |
687 ms |
42248 KB |
Output is correct |
49 |
Correct |
679 ms |
39300 KB |
Output is correct |
50 |
Correct |
362 ms |
27216 KB |
Output is correct |
51 |
Correct |
795 ms |
49016 KB |
Output is correct |
52 |
Correct |
74 ms |
17244 KB |
Output is correct |
53 |
Correct |
498 ms |
29864 KB |
Output is correct |
54 |
Correct |
860 ms |
50472 KB |
Output is correct |
55 |
Correct |
695 ms |
39944 KB |
Output is correct |
56 |
Correct |
497 ms |
30036 KB |
Output is correct |
57 |
Correct |
596 ms |
34344 KB |
Output is correct |
58 |
Correct |
530 ms |
32888 KB |
Output is correct |
59 |
Correct |
545 ms |
31572 KB |
Output is correct |
60 |
Correct |
389 ms |
30284 KB |
Output is correct |
61 |
Correct |
871 ms |
46288 KB |
Output is correct |
62 |
Correct |
659 ms |
38732 KB |
Output is correct |
63 |
Correct |
786 ms |
38960 KB |
Output is correct |
64 |
Correct |
293 ms |
30660 KB |
Output is correct |
65 |
Correct |
661 ms |
43804 KB |
Output is correct |
66 |
Correct |
677 ms |
40344 KB |
Output is correct |
67 |
Correct |
51 ms |
17236 KB |
Output is correct |
68 |
Correct |
290 ms |
29508 KB |
Output is correct |
69 |
Correct |
352 ms |
29340 KB |
Output is correct |
70 |
Correct |
542 ms |
29312 KB |
Output is correct |
71 |
Correct |
817 ms |
48584 KB |
Output is correct |
72 |
Correct |
669 ms |
38816 KB |
Output is correct |
73 |
Correct |
490 ms |
29012 KB |
Output is correct |
74 |
Correct |
560 ms |
33152 KB |
Output is correct |
75 |
Correct |
537 ms |
30796 KB |
Output is correct |
76 |
Correct |
507 ms |
30604 KB |
Output is correct |
77 |
Correct |
375 ms |
29384 KB |
Output is correct |
78 |
Correct |
804 ms |
43588 KB |
Output is correct |
79 |
Correct |
737 ms |
41224 KB |
Output is correct |
80 |
Correct |
750 ms |
37256 KB |
Output is correct |
81 |
Correct |
282 ms |
29384 KB |
Output is correct |
82 |
Correct |
678 ms |
42300 KB |
Output is correct |
83 |
Correct |
629 ms |
39284 KB |
Output is correct |
84 |
Correct |
483 ms |
29600 KB |
Output is correct |
85 |
Correct |
781 ms |
49300 KB |
Output is correct |
86 |
Correct |
670 ms |
39200 KB |
Output is correct |
87 |
Correct |
444 ms |
29268 KB |
Output is correct |
88 |
Correct |
558 ms |
33744 KB |
Output is correct |
89 |
Correct |
545 ms |
31728 KB |
Output is correct |
90 |
Correct |
508 ms |
30996 KB |
Output is correct |
91 |
Correct |
409 ms |
29760 KB |
Output is correct |
92 |
Correct |
919 ms |
48512 KB |
Output is correct |
93 |
Correct |
592 ms |
36532 KB |
Output is correct |
94 |
Correct |
591 ms |
34512 KB |
Output is correct |
95 |
Correct |
284 ms |
30132 KB |
Output is correct |
96 |
Correct |
652 ms |
43336 KB |
Output is correct |
97 |
Correct |
644 ms |
39616 KB |
Output is correct |
98 |
Correct |
478 ms |
29884 KB |
Output is correct |
99 |
Correct |
799 ms |
50132 KB |
Output is correct |
100 |
Correct |
704 ms |
39940 KB |
Output is correct |
101 |
Correct |
450 ms |
30016 KB |
Output is correct |
102 |
Correct |
539 ms |
33112 KB |
Output is correct |
103 |
Correct |
522 ms |
31892 KB |
Output is correct |
104 |
Correct |
519 ms |
31524 KB |
Output is correct |
105 |
Correct |
372 ms |
30152 KB |
Output is correct |
106 |
Correct |
727 ms |
41452 KB |
Output is correct |
107 |
Correct |
701 ms |
41752 KB |
Output is correct |
108 |
Correct |
654 ms |
36128 KB |
Output is correct |
109 |
Correct |
284 ms |
30468 KB |
Output is correct |
110 |
Correct |
651 ms |
43908 KB |
Output is correct |
111 |
Correct |
674 ms |
40132 KB |
Output is correct |