#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int k = 19;
const int inf = 1e8;
struct persistent_segtree{
struct node{
int sm;
int l, r;
node(){
sm = 0LL;
l = -1, r = -1;
}
node(int _sm){
sm = _sm;
l = -1, r = -1;
}
node(int _sm, int _l, int _r){
l = _l, r = _r, sm = _sm;
}
};
vector<node> v;
int k;
persistent_segtree(int n){
k = 1;
while(k <= n) k*=2; k*=2;
v.resize(k, node(0));
for(int i = 1; 2*i+1 < k; i++) v[i].l = 2*i, v[i].r = 2*i+1;
}
int upd(int nd, int a, int b, int in, int x){
if(a == b){
v.pb(node(x));
return (int)v.size() - 1;
}
int md = (a+b)/2;
if(in <= md){
int rt = upd(v[nd].l, a, md, in, x);
v.pb(node(v[v[nd].r].sm+v[rt].sm, rt, v[nd].r));
return (int)v.size()-1;
}
else{
int rt = upd(v[nd].r, md+1, b, in, x);
v.pb(node(v[v[nd].l].sm+v[rt].sm, v[nd].l, rt));
return (int)v.size()-1;
}
}
int upd(int nd, int in, int x){
return upd(nd, 0, k/2-1, in, x);
}
int sum(int l, int r, int nd, int a, int b){
if(a > r || b < l){
return 0;
}
if(a >= l && b <= r){
return v[nd].sm;
}
int md = (a+b)/2;
return sum(l, r, v[nd].l, a, md) + sum(l, r, v[nd].r, md+1, b);
}
int sum(int nd, int l, int r){
return sum(l, r, nd, 0, k/2-1);
}
};
int n, m;
vector<int> C;
vector<vector<int>> v;
vector<vector<pair<int, int>>> anc;
vector<int> cnt;
vector<int> pss;
vector<int> mxh;
vector<int> ans;
persistent_segtree ps(0);
pair<int, int> next(int nd, int h){
if(h == 0) return {nd, 0};
for(int i = k-1; i >= 0; i--){
if(anc[nd][i].sc <= h){
h-=anc[nd][i].sc;
auto nxt = next(anc[nd][i].f, h);
nxt.sc+=anc[nd][i].sc;
return nxt;
}
}
return {anc[nd][0].f, anc[nd][0].sc};
}
void dfs0(int nd, int ss){
for(int x: v[nd]) if(x != ss) dfs0(x, nd);
int mx = 0, smx = 0, in = n;
for(int x: v[nd]) if(x != ss){
if(mxh[x] > mx) smx = mx, mx = mxh[x], in = x;
else if(mxh[x] > smx) smx = mxh[x];
}
mxh[nd] = mxh[in]+1;
auto nxt = next(in, smx);
nxt.sc++;
nxt.sc = min(nxt.sc, inf);
anc[nd][0] = nxt;
for(int i = 1; i < k; i++){
anc[nd][i].f = anc[anc[nd][i-1].f][i-1].f;
anc[nd][i].sc = anc[nd][i-1].sc + anc[anc[nd][i-1].f][i-1].sc;
anc[nd][i].sc = min(anc[nd][i].sc, inf);
}
cnt[nd] = cnt[nxt.f];
pss[nd] = pss[nxt.f];
if(ps.sum(pss[nd], C[nd], C[nd]) == 0){
cnt[nd]++;
pss[nd] = ps.upd(pss[nd], C[nd], 1);
}
}
void dfs1(int nd, int ss){
vector<pair<int, int>> sth;
for(int x: v[nd]) sth.pb({mxh[x], x});
sort(sth.rbegin(), sth.rend());
while(sth.size() < 3) sth.pb({0, n});
auto nxt = next(sth[0].sc, sth[1].f);
ans[nd] = cnt[nxt.f];
auto old_anc = anc[nd];
int old_cnt = cnt[nd], old_mxh = mxh[nd];
auto old_pss = pss[nd];
for(int x: v[nd]) if(x != ss){
pair<int, int> nxt;
if(x == sth[0].sc) nxt = next(sth[1].sc, sth[2].f), mxh[nd] = mxh[sth[1].sc]+1;
else if(x == sth[1].sc) nxt = next(sth[0].sc, sth[2].f), mxh[nd] = mxh[sth[0].sc]+1;
else nxt = next(sth[0].sc, sth[1].f), mxh[nd] = mxh[sth[0].sc]+1;
nxt.sc++;
nxt.sc = min(nxt.sc, inf);
anc[nd][0] = nxt;
for(int i = 1; i < k; i++){
anc[nd][i].f = anc[anc[nd][i-1].f][i-1].f;
anc[nd][i].sc = anc[nd][i-1].sc + anc[anc[nd][i-1].f][i-1].sc;
anc[nd][i].sc = min(anc[nd][i].sc, inf);
}
cnt[nd] = cnt[nxt.f];
pss[nd] = pss[nxt.f];
if(ps.sum(pss[nd], C[nd], C[nd]) == 0){
cnt[nd]++;
pss[nd] = ps.upd(pss[nd], C[nd], 1);
}
dfs1(x, nd);
}
anc[nd] = old_anc;
cnt[nd] = old_cnt;
mxh[nd] = old_mxh;
pss[nd] = old_pss;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
C.resize(n);
v.resize(n);
anc.resize(n+1, vector<pair<int, int>>(k, {n, inf}));
cnt.resize(n+1, 0);
mxh.resize(n+1, 1);
mxh[n] = 0;
ans.resize(n);
for(int i = 0; i < n-1; i++){
int a, b; cin >> a >> b; a--, b--;
v[a].pb(b);
v[b].pb(a);
}
for(int &x: C) cin >> x, x--;
ps = persistent_segtree(m);
pss.resize(n+1, 1);
dfs0(0, -1);
dfs1(0, -1);
for(int x: ans) cout << x << "\n";
}
Compilation message
joi2019_ho_t5.cpp: In constructor 'persistent_segtree::persistent_segtree(int)':
joi2019_ho_t5.cpp:31:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
31 | while(k <= n) k*=2; k*=2;
| ^~~~~
joi2019_ho_t5.cpp:31:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
31 | while(k <= n) k*=2; k*=2;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
4 ms |
1640 KB |
Output is correct |
3 |
Correct |
2 ms |
932 KB |
Output is correct |
4 |
Correct |
4 ms |
1352 KB |
Output is correct |
5 |
Correct |
3 ms |
1176 KB |
Output is correct |
6 |
Correct |
3 ms |
1228 KB |
Output is correct |
7 |
Correct |
3 ms |
1100 KB |
Output is correct |
8 |
Correct |
3 ms |
1276 KB |
Output is correct |
9 |
Correct |
3 ms |
1412 KB |
Output is correct |
10 |
Correct |
3 ms |
1088 KB |
Output is correct |
11 |
Correct |
3 ms |
1168 KB |
Output is correct |
12 |
Correct |
3 ms |
1192 KB |
Output is correct |
13 |
Correct |
4 ms |
1228 KB |
Output is correct |
14 |
Correct |
3 ms |
1100 KB |
Output is correct |
15 |
Correct |
4 ms |
1228 KB |
Output is correct |
16 |
Correct |
3 ms |
1188 KB |
Output is correct |
17 |
Correct |
4 ms |
1484 KB |
Output is correct |
18 |
Correct |
3 ms |
1084 KB |
Output is correct |
19 |
Correct |
4 ms |
1784 KB |
Output is correct |
20 |
Correct |
5 ms |
1904 KB |
Output is correct |
21 |
Correct |
4 ms |
1800 KB |
Output is correct |
22 |
Correct |
4 ms |
1748 KB |
Output is correct |
23 |
Correct |
4 ms |
1800 KB |
Output is correct |
24 |
Correct |
4 ms |
1752 KB |
Output is correct |
25 |
Correct |
4 ms |
1784 KB |
Output is correct |
26 |
Correct |
4 ms |
1760 KB |
Output is correct |
27 |
Correct |
6 ms |
1788 KB |
Output is correct |
28 |
Correct |
4 ms |
1792 KB |
Output is correct |
29 |
Correct |
6 ms |
1788 KB |
Output is correct |
30 |
Correct |
4 ms |
1728 KB |
Output is correct |
31 |
Correct |
5 ms |
1424 KB |
Output is correct |
32 |
Correct |
4 ms |
1800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
220 ms |
34624 KB |
Output is correct |
2 |
Correct |
566 ms |
72792 KB |
Output is correct |
3 |
Correct |
74 ms |
12884 KB |
Output is correct |
4 |
Correct |
419 ms |
56364 KB |
Output is correct |
5 |
Correct |
1055 ms |
100724 KB |
Output is correct |
6 |
Correct |
771 ms |
95020 KB |
Output is correct |
7 |
Correct |
403 ms |
56880 KB |
Output is correct |
8 |
Correct |
451 ms |
62540 KB |
Output is correct |
9 |
Correct |
438 ms |
64792 KB |
Output is correct |
10 |
Correct |
430 ms |
61680 KB |
Output is correct |
11 |
Correct |
345 ms |
69488 KB |
Output is correct |
12 |
Correct |
782 ms |
111460 KB |
Output is correct |
13 |
Correct |
673 ms |
80528 KB |
Output is correct |
14 |
Correct |
734 ms |
86456 KB |
Output is correct |
15 |
Correct |
353 ms |
69752 KB |
Output is correct |
16 |
Correct |
798 ms |
87128 KB |
Output is correct |
17 |
Correct |
779 ms |
86400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
631 ms |
141028 KB |
Output is correct |
2 |
Correct |
1629 ms |
194300 KB |
Output is correct |
3 |
Correct |
122 ms |
39852 KB |
Output is correct |
4 |
Correct |
787 ms |
151580 KB |
Output is correct |
5 |
Correct |
1785 ms |
200504 KB |
Output is correct |
6 |
Correct |
1323 ms |
171880 KB |
Output is correct |
7 |
Correct |
779 ms |
151844 KB |
Output is correct |
8 |
Correct |
921 ms |
159624 KB |
Output is correct |
9 |
Correct |
838 ms |
157108 KB |
Output is correct |
10 |
Correct |
862 ms |
154524 KB |
Output is correct |
11 |
Correct |
751 ms |
151900 KB |
Output is correct |
12 |
Correct |
1545 ms |
188260 KB |
Output is correct |
13 |
Correct |
1100 ms |
168756 KB |
Output is correct |
14 |
Correct |
1185 ms |
179452 KB |
Output is correct |
15 |
Correct |
642 ms |
153112 KB |
Output is correct |
16 |
Correct |
1311 ms |
180292 KB |
Output is correct |
17 |
Correct |
1269 ms |
172332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
4 ms |
1640 KB |
Output is correct |
3 |
Correct |
2 ms |
932 KB |
Output is correct |
4 |
Correct |
4 ms |
1352 KB |
Output is correct |
5 |
Correct |
3 ms |
1176 KB |
Output is correct |
6 |
Correct |
3 ms |
1228 KB |
Output is correct |
7 |
Correct |
3 ms |
1100 KB |
Output is correct |
8 |
Correct |
3 ms |
1276 KB |
Output is correct |
9 |
Correct |
3 ms |
1412 KB |
Output is correct |
10 |
Correct |
3 ms |
1088 KB |
Output is correct |
11 |
Correct |
3 ms |
1168 KB |
Output is correct |
12 |
Correct |
3 ms |
1192 KB |
Output is correct |
13 |
Correct |
4 ms |
1228 KB |
Output is correct |
14 |
Correct |
3 ms |
1100 KB |
Output is correct |
15 |
Correct |
4 ms |
1228 KB |
Output is correct |
16 |
Correct |
3 ms |
1188 KB |
Output is correct |
17 |
Correct |
4 ms |
1484 KB |
Output is correct |
18 |
Correct |
3 ms |
1084 KB |
Output is correct |
19 |
Correct |
4 ms |
1784 KB |
Output is correct |
20 |
Correct |
5 ms |
1904 KB |
Output is correct |
21 |
Correct |
4 ms |
1800 KB |
Output is correct |
22 |
Correct |
4 ms |
1748 KB |
Output is correct |
23 |
Correct |
4 ms |
1800 KB |
Output is correct |
24 |
Correct |
4 ms |
1752 KB |
Output is correct |
25 |
Correct |
4 ms |
1784 KB |
Output is correct |
26 |
Correct |
4 ms |
1760 KB |
Output is correct |
27 |
Correct |
6 ms |
1788 KB |
Output is correct |
28 |
Correct |
4 ms |
1792 KB |
Output is correct |
29 |
Correct |
6 ms |
1788 KB |
Output is correct |
30 |
Correct |
4 ms |
1728 KB |
Output is correct |
31 |
Correct |
5 ms |
1424 KB |
Output is correct |
32 |
Correct |
4 ms |
1800 KB |
Output is correct |
33 |
Correct |
220 ms |
34624 KB |
Output is correct |
34 |
Correct |
566 ms |
72792 KB |
Output is correct |
35 |
Correct |
74 ms |
12884 KB |
Output is correct |
36 |
Correct |
419 ms |
56364 KB |
Output is correct |
37 |
Correct |
1055 ms |
100724 KB |
Output is correct |
38 |
Correct |
771 ms |
95020 KB |
Output is correct |
39 |
Correct |
403 ms |
56880 KB |
Output is correct |
40 |
Correct |
451 ms |
62540 KB |
Output is correct |
41 |
Correct |
438 ms |
64792 KB |
Output is correct |
42 |
Correct |
430 ms |
61680 KB |
Output is correct |
43 |
Correct |
345 ms |
69488 KB |
Output is correct |
44 |
Correct |
782 ms |
111460 KB |
Output is correct |
45 |
Correct |
673 ms |
80528 KB |
Output is correct |
46 |
Correct |
734 ms |
86456 KB |
Output is correct |
47 |
Correct |
353 ms |
69752 KB |
Output is correct |
48 |
Correct |
798 ms |
87128 KB |
Output is correct |
49 |
Correct |
779 ms |
86400 KB |
Output is correct |
50 |
Correct |
631 ms |
141028 KB |
Output is correct |
51 |
Correct |
1629 ms |
194300 KB |
Output is correct |
52 |
Correct |
122 ms |
39852 KB |
Output is correct |
53 |
Correct |
787 ms |
151580 KB |
Output is correct |
54 |
Correct |
1785 ms |
200504 KB |
Output is correct |
55 |
Correct |
1323 ms |
171880 KB |
Output is correct |
56 |
Correct |
779 ms |
151844 KB |
Output is correct |
57 |
Correct |
921 ms |
159624 KB |
Output is correct |
58 |
Correct |
838 ms |
157108 KB |
Output is correct |
59 |
Correct |
862 ms |
154524 KB |
Output is correct |
60 |
Correct |
751 ms |
151900 KB |
Output is correct |
61 |
Correct |
1545 ms |
188260 KB |
Output is correct |
62 |
Correct |
1100 ms |
168756 KB |
Output is correct |
63 |
Correct |
1185 ms |
179452 KB |
Output is correct |
64 |
Correct |
642 ms |
153112 KB |
Output is correct |
65 |
Correct |
1311 ms |
180292 KB |
Output is correct |
66 |
Correct |
1269 ms |
172332 KB |
Output is correct |
67 |
Correct |
76 ms |
19880 KB |
Output is correct |
68 |
Correct |
496 ms |
74924 KB |
Output is correct |
69 |
Correct |
644 ms |
97024 KB |
Output is correct |
70 |
Correct |
457 ms |
77828 KB |
Output is correct |
71 |
Correct |
1198 ms |
111244 KB |
Output is correct |
72 |
Correct |
807 ms |
91952 KB |
Output is correct |
73 |
Correct |
438 ms |
78108 KB |
Output is correct |
74 |
Correct |
474 ms |
75220 KB |
Output is correct |
75 |
Correct |
497 ms |
69252 KB |
Output is correct |
76 |
Correct |
472 ms |
81152 KB |
Output is correct |
77 |
Correct |
409 ms |
79928 KB |
Output is correct |
78 |
Correct |
930 ms |
93880 KB |
Output is correct |
79 |
Correct |
819 ms |
109212 KB |
Output is correct |
80 |
Correct |
793 ms |
100060 KB |
Output is correct |
81 |
Correct |
395 ms |
81972 KB |
Output is correct |
82 |
Correct |
919 ms |
119620 KB |
Output is correct |
83 |
Correct |
833 ms |
89300 KB |
Output is correct |
84 |
Correct |
540 ms |
102504 KB |
Output is correct |
85 |
Correct |
1213 ms |
125088 KB |
Output is correct |
86 |
Correct |
869 ms |
95672 KB |
Output is correct |
87 |
Correct |
532 ms |
102836 KB |
Output is correct |
88 |
Correct |
560 ms |
88884 KB |
Output is correct |
89 |
Correct |
609 ms |
104944 KB |
Output is correct |
90 |
Correct |
557 ms |
104324 KB |
Output is correct |
91 |
Correct |
491 ms |
104492 KB |
Output is correct |
92 |
Correct |
1179 ms |
122540 KB |
Output is correct |
93 |
Correct |
657 ms |
103012 KB |
Output is correct |
94 |
Correct |
630 ms |
87688 KB |
Output is correct |
95 |
Correct |
427 ms |
106476 KB |
Output is correct |
96 |
Correct |
905 ms |
108416 KB |
Output is correct |
97 |
Correct |
849 ms |
91992 KB |
Output is correct |
98 |
Correct |
837 ms |
150952 KB |
Output is correct |
99 |
Correct |
1216 ms |
130300 KB |
Output is correct |
100 |
Correct |
1302 ms |
167384 KB |
Output is correct |
101 |
Correct |
712 ms |
151528 KB |
Output is correct |
102 |
Correct |
744 ms |
154696 KB |
Output is correct |
103 |
Correct |
792 ms |
154140 KB |
Output is correct |
104 |
Correct |
777 ms |
154112 KB |
Output is correct |
105 |
Correct |
613 ms |
152876 KB |
Output is correct |
106 |
Correct |
1145 ms |
169736 KB |
Output is correct |
107 |
Correct |
982 ms |
132536 KB |
Output is correct |
108 |
Correct |
1113 ms |
164552 KB |
Output is correct |
109 |
Correct |
652 ms |
154544 KB |
Output is correct |
110 |
Correct |
1081 ms |
120128 KB |
Output is correct |
111 |
Correct |
1165 ms |
169476 KB |
Output is correct |