#include <bits/stdc++.h>
using namespace std;
vector<int> segTree;
vector<vector<int>> g;
vector<int> path;
vector<int> dist;
map<int,int> uc;
vector<int> fs;
vector<int> ans;
vector<int> dp;
vector<int> c;
int v1 = -1,v2 = -1,n = -1;
void modify(int i,int x,int l,int r,int indV)
{
if(i > r || i < l)
return ;
else if(l == r)
{
segTree[indV] += x;
return ;
}
int m = (l+r)/2;
modify(i,x,l,m,indV*2+1);
modify(i,x,m+1,r,indV*2+2);
segTree[indV] = segTree[indV*2+1] + segTree[indV*2+2];
return ;
}
int get(int lx,int rx,int l,int r,int indV)
{
if(l > rx || r < lx)
return 0;
else if(l >= lx && r <= rx)
{
return segTree[indV];
}
int m = (l+r)/2;
int sl = get(lx,rx,l,m,indV*2+1);
int sr = get(lx,rx,m+1,r,indV*2+2);
return sl+sr;
}
pair<int,int> dfsf(int v,int p)
{
int tv = v,td = 0;
for(auto u:g[v])
{
if(u != p)
{
pair<int,int> ck = dfsf(u,v);
if(ck.second+1 > td)
{
td = ck.second+1;
tv = ck.first;
}
}
}
return {tv,td};
}
void dfsd(int v,int p,int d)
{
dist[v] = d;
for(auto u:g[v])
{
if(u != p)
{
dfsd(u,v,d+1);
}
}
return ;
}
void dfsdp(int v,int p)
{
dp[v] = 0;
for(auto u:g[v])
{
if(u != p)
{
dfsdp(u,v);
dp[v] = max(dp[v],dp[u]+1);
}
}
return ;
}
void dfs(int v,int p,int b)
{
//cout << v << ' ' << dp[v] << ' ' << fs[v] << ' ' << uc.size() << ' ' << (uc.size() != 0 ? (*uc.begin()).first : -1) << "\n";
path.push_back(v);
if(b == fs[v])
ans[v] = uc.size();
multiset<int> gl;
for(auto u:g[v])
{
if(u != p)
{
gl.insert(-dp[u]);
}
}
for(auto u:g[v])
{
if(u != p)
{
gl.erase(gl.find(-dp[u]));
if(gl.size() != 0)
{
int mg = -(*gl.begin());
modify(max(0,int(int(path.size())-mg-2)),1,0,n-1,0);
modify(int(path.size())-1,-1,0,n-1,0);
int fu = int(path.size())-dp[u]-1,su = int(path.size())-dp[u]-2;
/* if(u == 1)
{
cout << mg << ' ' << fu << ' ' << su << "\n";
}*/
if(fu >= 0 && get(0,fu,0,n-1,0) == 0)
{
uc[c[path[fu]]]++;
}
if(su >= 0 && get(0,su,0,n-1,0) == 0)
{
uc[c[path[su]]]++;
}
dfs(u,v,b);
if(fu >= 0 && get(0,fu,0,n-1,0) == 0)
{
uc[c[path[fu]]]--;
if(!uc[c[path[fu]]])
uc.erase(c[path[fu]]);
}
if(su >= 0 && get(0,su,0,n-1,0) == 0)
{
uc[c[path[su]]]--;
if(!uc[c[path[su]]])
uc.erase(c[path[su]]);
}
modify(max(0,int(int(path.size())-mg-2)),-1,0,n-1,0);
modify(int(path.size())-1,1,0,n-1,0);
}
else
{
int fu = int(path.size())-dp[u]-1,su = int(path.size())-dp[u]-2;
if(fu >= 0 && get(0,fu,0,n-1,0) == 0)
{
uc[c[path[fu]]]++;
}
if(su >= 0 && get(0,su,0,n-1,0) == 0)
{
uc[c[path[su]]]++;
}
dfs(u,v,b);
if(fu >= 0 && get(0,fu,0,n-1,0) == 0)
{
uc[c[path[fu]]]--;
if(!uc[c[path[fu]]])
uc.erase(c[path[fu]]);
}
if(su >= 0 && get(0,su,0,n-1,0) == 0)
{
uc[c[path[su]]]--;
if(!uc[c[path[su]]])
uc.erase(c[path[su]]);
}
}
gl.insert(-dp[u]);
}
}
path.pop_back();
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int m;
cin >> n >> m;
segTree.resize(4*n);
g.resize(n);
dist.resize(n);
fs.resize(n);
ans.resize(n);
dp.resize(n);
c.resize(n);
for(int i = 0;i < n-1;++i)
{
int a,b;
cin >> a >> b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
//cout << 1;
for(int i = 0;i < n;++i)
cin >> c[i];
v1 = dfsf(0,-1).first;
v2 = dfsf(v1,-1).first;
dfsd(v1,-1,0);
vector<int> d2 = dist;
dfsd(v2,-1,0);
//cout << 1;
for(int j =0 ;j < n;++j)
{
if(d2[j] > dist[j])
{
fs[j] = 1;
}
else
fs[j] = 2;
}
// cout << v1 << ' ' << v2 << ' ';
//cout << 1;
dfsdp(v1,-1);
dfs(v1,-1,1);
dfsdp(v2,-1);
dfs(v2,-1,2);
// cout << 1;
for(int j = 0;j < n;++j)
{
cout << ans[j] << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
3 ms |
860 KB |
Output is correct |
5 |
Correct |
4 ms |
604 KB |
Output is correct |
6 |
Correct |
3 ms |
1116 KB |
Output is correct |
7 |
Correct |
3 ms |
860 KB |
Output is correct |
8 |
Correct |
4 ms |
692 KB |
Output is correct |
9 |
Correct |
4 ms |
604 KB |
Output is correct |
10 |
Correct |
3 ms |
604 KB |
Output is correct |
11 |
Correct |
4 ms |
716 KB |
Output is correct |
12 |
Correct |
4 ms |
604 KB |
Output is correct |
13 |
Correct |
3 ms |
860 KB |
Output is correct |
14 |
Correct |
3 ms |
860 KB |
Output is correct |
15 |
Correct |
3 ms |
860 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
3 ms |
860 KB |
Output is correct |
18 |
Correct |
3 ms |
860 KB |
Output is correct |
19 |
Correct |
3 ms |
604 KB |
Output is correct |
20 |
Correct |
3 ms |
1116 KB |
Output is correct |
21 |
Correct |
3 ms |
860 KB |
Output is correct |
22 |
Correct |
3 ms |
604 KB |
Output is correct |
23 |
Correct |
4 ms |
660 KB |
Output is correct |
24 |
Correct |
4 ms |
604 KB |
Output is correct |
25 |
Correct |
4 ms |
724 KB |
Output is correct |
26 |
Correct |
4 ms |
604 KB |
Output is correct |
27 |
Correct |
4 ms |
860 KB |
Output is correct |
28 |
Correct |
4 ms |
976 KB |
Output is correct |
29 |
Correct |
4 ms |
860 KB |
Output is correct |
30 |
Correct |
5 ms |
604 KB |
Output is correct |
31 |
Correct |
3 ms |
860 KB |
Output is correct |
32 |
Correct |
4 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
278 ms |
13140 KB |
Output is correct |
2 |
Correct |
180 ms |
38644 KB |
Output is correct |
3 |
Correct |
40 ms |
6816 KB |
Output is correct |
4 |
Correct |
523 ms |
22868 KB |
Output is correct |
5 |
Correct |
445 ms |
67376 KB |
Output is correct |
6 |
Correct |
440 ms |
44880 KB |
Output is correct |
7 |
Correct |
539 ms |
24332 KB |
Output is correct |
8 |
Correct |
555 ms |
28352 KB |
Output is correct |
9 |
Correct |
491 ms |
26836 KB |
Output is correct |
10 |
Correct |
547 ms |
26556 KB |
Output is correct |
11 |
Correct |
549 ms |
32132 KB |
Output is correct |
12 |
Correct |
580 ms |
52812 KB |
Output is correct |
13 |
Correct |
557 ms |
47768 KB |
Output is correct |
14 |
Correct |
556 ms |
45500 KB |
Output is correct |
15 |
Correct |
620 ms |
32516 KB |
Output is correct |
16 |
Correct |
452 ms |
55500 KB |
Output is correct |
17 |
Correct |
531 ms |
47260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
427 ms |
18964 KB |
Output is correct |
2 |
Correct |
701 ms |
74692 KB |
Output is correct |
3 |
Correct |
58 ms |
7928 KB |
Output is correct |
4 |
Correct |
539 ms |
23520 KB |
Output is correct |
5 |
Correct |
791 ms |
78276 KB |
Output is correct |
6 |
Correct |
608 ms |
48332 KB |
Output is correct |
7 |
Correct |
549 ms |
24852 KB |
Output is correct |
8 |
Correct |
573 ms |
34576 KB |
Output is correct |
9 |
Correct |
627 ms |
31348 KB |
Output is correct |
10 |
Correct |
531 ms |
28168 KB |
Output is correct |
11 |
Correct |
519 ms |
28476 KB |
Output is correct |
12 |
Correct |
741 ms |
67272 KB |
Output is correct |
13 |
Correct |
583 ms |
48328 KB |
Output is correct |
14 |
Correct |
580 ms |
47564 KB |
Output is correct |
15 |
Correct |
549 ms |
33588 KB |
Output is correct |
16 |
Correct |
656 ms |
63304 KB |
Output is correct |
17 |
Correct |
545 ms |
50988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
3 ms |
860 KB |
Output is correct |
5 |
Correct |
4 ms |
604 KB |
Output is correct |
6 |
Correct |
3 ms |
1116 KB |
Output is correct |
7 |
Correct |
3 ms |
860 KB |
Output is correct |
8 |
Correct |
4 ms |
692 KB |
Output is correct |
9 |
Correct |
4 ms |
604 KB |
Output is correct |
10 |
Correct |
3 ms |
604 KB |
Output is correct |
11 |
Correct |
4 ms |
716 KB |
Output is correct |
12 |
Correct |
4 ms |
604 KB |
Output is correct |
13 |
Correct |
3 ms |
860 KB |
Output is correct |
14 |
Correct |
3 ms |
860 KB |
Output is correct |
15 |
Correct |
3 ms |
860 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
3 ms |
860 KB |
Output is correct |
18 |
Correct |
3 ms |
860 KB |
Output is correct |
19 |
Correct |
3 ms |
604 KB |
Output is correct |
20 |
Correct |
3 ms |
1116 KB |
Output is correct |
21 |
Correct |
3 ms |
860 KB |
Output is correct |
22 |
Correct |
3 ms |
604 KB |
Output is correct |
23 |
Correct |
4 ms |
660 KB |
Output is correct |
24 |
Correct |
4 ms |
604 KB |
Output is correct |
25 |
Correct |
4 ms |
724 KB |
Output is correct |
26 |
Correct |
4 ms |
604 KB |
Output is correct |
27 |
Correct |
4 ms |
860 KB |
Output is correct |
28 |
Correct |
4 ms |
976 KB |
Output is correct |
29 |
Correct |
4 ms |
860 KB |
Output is correct |
30 |
Correct |
5 ms |
604 KB |
Output is correct |
31 |
Correct |
3 ms |
860 KB |
Output is correct |
32 |
Correct |
4 ms |
860 KB |
Output is correct |
33 |
Correct |
278 ms |
13140 KB |
Output is correct |
34 |
Correct |
180 ms |
38644 KB |
Output is correct |
35 |
Correct |
40 ms |
6816 KB |
Output is correct |
36 |
Correct |
523 ms |
22868 KB |
Output is correct |
37 |
Correct |
445 ms |
67376 KB |
Output is correct |
38 |
Correct |
440 ms |
44880 KB |
Output is correct |
39 |
Correct |
539 ms |
24332 KB |
Output is correct |
40 |
Correct |
555 ms |
28352 KB |
Output is correct |
41 |
Correct |
491 ms |
26836 KB |
Output is correct |
42 |
Correct |
547 ms |
26556 KB |
Output is correct |
43 |
Correct |
549 ms |
32132 KB |
Output is correct |
44 |
Correct |
580 ms |
52812 KB |
Output is correct |
45 |
Correct |
557 ms |
47768 KB |
Output is correct |
46 |
Correct |
556 ms |
45500 KB |
Output is correct |
47 |
Correct |
620 ms |
32516 KB |
Output is correct |
48 |
Correct |
452 ms |
55500 KB |
Output is correct |
49 |
Correct |
531 ms |
47260 KB |
Output is correct |
50 |
Correct |
427 ms |
18964 KB |
Output is correct |
51 |
Correct |
701 ms |
74692 KB |
Output is correct |
52 |
Correct |
58 ms |
7928 KB |
Output is correct |
53 |
Correct |
539 ms |
23520 KB |
Output is correct |
54 |
Correct |
791 ms |
78276 KB |
Output is correct |
55 |
Correct |
608 ms |
48332 KB |
Output is correct |
56 |
Correct |
549 ms |
24852 KB |
Output is correct |
57 |
Correct |
573 ms |
34576 KB |
Output is correct |
58 |
Correct |
627 ms |
31348 KB |
Output is correct |
59 |
Correct |
531 ms |
28168 KB |
Output is correct |
60 |
Correct |
519 ms |
28476 KB |
Output is correct |
61 |
Correct |
741 ms |
67272 KB |
Output is correct |
62 |
Correct |
583 ms |
48328 KB |
Output is correct |
63 |
Correct |
580 ms |
47564 KB |
Output is correct |
64 |
Correct |
549 ms |
33588 KB |
Output is correct |
65 |
Correct |
656 ms |
63304 KB |
Output is correct |
66 |
Correct |
545 ms |
50988 KB |
Output is correct |
67 |
Correct |
52 ms |
3684 KB |
Output is correct |
68 |
Correct |
212 ms |
31052 KB |
Output is correct |
69 |
Correct |
298 ms |
29344 KB |
Output is correct |
70 |
Correct |
460 ms |
22612 KB |
Output is correct |
71 |
Correct |
432 ms |
67360 KB |
Output is correct |
72 |
Correct |
516 ms |
44888 KB |
Output is correct |
73 |
Correct |
497 ms |
23884 KB |
Output is correct |
74 |
Correct |
509 ms |
33192 KB |
Output is correct |
75 |
Correct |
500 ms |
28180 KB |
Output is correct |
76 |
Correct |
524 ms |
27112 KB |
Output is correct |
77 |
Correct |
523 ms |
28308 KB |
Output is correct |
78 |
Correct |
533 ms |
57336 KB |
Output is correct |
79 |
Correct |
527 ms |
52684 KB |
Output is correct |
80 |
Correct |
583 ms |
43168 KB |
Output is correct |
81 |
Correct |
592 ms |
32328 KB |
Output is correct |
82 |
Correct |
506 ms |
55620 KB |
Output is correct |
83 |
Correct |
436 ms |
47236 KB |
Output is correct |
84 |
Correct |
495 ms |
22964 KB |
Output is correct |
85 |
Correct |
460 ms |
67856 KB |
Output is correct |
86 |
Correct |
519 ms |
45376 KB |
Output is correct |
87 |
Correct |
543 ms |
23992 KB |
Output is correct |
88 |
Correct |
532 ms |
34184 KB |
Output is correct |
89 |
Correct |
531 ms |
29208 KB |
Output is correct |
90 |
Correct |
585 ms |
27796 KB |
Output is correct |
91 |
Correct |
543 ms |
28648 KB |
Output is correct |
92 |
Correct |
511 ms |
66504 KB |
Output is correct |
93 |
Correct |
584 ms |
41784 KB |
Output is correct |
94 |
Correct |
550 ms |
36952 KB |
Output is correct |
95 |
Correct |
545 ms |
32852 KB |
Output is correct |
96 |
Correct |
523 ms |
56128 KB |
Output is correct |
97 |
Correct |
511 ms |
48008 KB |
Output is correct |
98 |
Correct |
548 ms |
23468 KB |
Output is correct |
99 |
Correct |
574 ms |
68220 KB |
Output is correct |
100 |
Correct |
651 ms |
47804 KB |
Output is correct |
101 |
Correct |
499 ms |
25448 KB |
Output is correct |
102 |
Correct |
628 ms |
32336 KB |
Output is correct |
103 |
Correct |
560 ms |
29136 KB |
Output is correct |
104 |
Correct |
601 ms |
28072 KB |
Output is correct |
105 |
Correct |
569 ms |
29644 KB |
Output is correct |
106 |
Correct |
628 ms |
52896 KB |
Output is correct |
107 |
Correct |
565 ms |
53704 KB |
Output is correct |
108 |
Correct |
618 ms |
40328 KB |
Output is correct |
109 |
Correct |
569 ms |
33412 KB |
Output is correct |
110 |
Correct |
692 ms |
58164 KB |
Output is correct |
111 |
Correct |
602 ms |
50192 KB |
Output is correct |