#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=2e5+10;
const int INF=1e9;
vector <int> diff;
vector <int> v[MAXN], vc[MAXN], ch[MAXN];
int col[MAXN], ans;
int par[MAXN], in[MAXN], out[MAXN], cnt;
int d[MAXN];
bool seen[MAXN], used[MAXN];
int n, k;
void find_ss(int x, int p) {
d[x]=1;
for (auto i:v[x]) {
if (i==p || seen[i]) continue;
find_ss(i,x);
d[x]+=d[i];
}
}
int find_centroid(int x, int ss) {
for (auto i:v[x]) {
if (seen[x]) continue;
if (d[i]>d[x]) continue;
if (d[i]*2>ss) return find_centroid(i,ss);
}
return x;
}
int decompose(int x) {
find_ss(x,-1);
int cur=find_centroid(x,d[x]);
seen[cur]=true;
for (auto i:v[cur]) {
if (seen[i]) continue;
int to=decompose(i);
ch[cur].push_back(to);
}
return cur;
}
void dfs_cent(int x) {
in[x]=cnt;
cnt++;
for (auto i:ch[x]) dfs_cent(i);
out[x]=cnt;
cnt++;
}
void dfs(int x, int p) {
for (auto i:v[x]) {
if (i==p || seen[i]) continue;
par[i]=x;
dfs(i,x);
}
}
bool in_subtree(int x, int i) {
return (in[x]<=in[i] && out[x]>=out[i]);
}
void bfs_ans(int start) {
if (!diff.empty()) diff.clear();
queue <int> q;
diff.push_back(col[start]);
q.push(col[start]);
used[col[start]]=true;
int s=0;
bool fl=false;
while (!q.empty()) {
int x=q.front();
q.pop();
s++;
for (auto i:vc[x]) {
if (!in_subtree(start,i)) {
fl=true;
break;
}
if (par[i]!=0 && !used[col[par[i]]]) {
used[col[par[i]]]=true;
q.push(col[par[i]]);
diff.push_back(col[par[i]]);
}
}
if (fl) break;
}
if (!fl) ans=min(ans,s-1);
for (auto i:diff) used[i]=false;
}
void find_ans(int x) {
par[x]=0;
dfs(x,-1);
bfs_ans(x);
seen[x]=true;
for (auto i:ch[x]) find_ans(i);
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
cin >> n >> k;
for (int i=0;i<n-1;i++) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for (int i=1;i<=n;i++) {
cin >> col[i];
vc[col[i]].push_back(i);
}
ans=INF;
int start=decompose(1);
dfs_cent(start);
for (int i=1;i<=n;i++) seen[i]=false;
find_ans(start);
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
18524 KB |
Output is correct |
2 |
Correct |
5 ms |
18780 KB |
Output is correct |
3 |
Correct |
4 ms |
18524 KB |
Output is correct |
4 |
Correct |
4 ms |
18524 KB |
Output is correct |
5 |
Correct |
4 ms |
18524 KB |
Output is correct |
6 |
Correct |
4 ms |
18524 KB |
Output is correct |
7 |
Correct |
5 ms |
18524 KB |
Output is correct |
8 |
Correct |
4 ms |
18524 KB |
Output is correct |
9 |
Correct |
5 ms |
18520 KB |
Output is correct |
10 |
Correct |
4 ms |
18524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
18524 KB |
Output is correct |
2 |
Correct |
5 ms |
18780 KB |
Output is correct |
3 |
Correct |
4 ms |
18524 KB |
Output is correct |
4 |
Correct |
4 ms |
18524 KB |
Output is correct |
5 |
Correct |
4 ms |
18524 KB |
Output is correct |
6 |
Correct |
4 ms |
18524 KB |
Output is correct |
7 |
Correct |
5 ms |
18524 KB |
Output is correct |
8 |
Correct |
4 ms |
18524 KB |
Output is correct |
9 |
Correct |
5 ms |
18520 KB |
Output is correct |
10 |
Correct |
4 ms |
18524 KB |
Output is correct |
11 |
Correct |
5 ms |
18624 KB |
Output is correct |
12 |
Correct |
5 ms |
18780 KB |
Output is correct |
13 |
Correct |
7 ms |
18780 KB |
Output is correct |
14 |
Correct |
5 ms |
18780 KB |
Output is correct |
15 |
Correct |
5 ms |
18776 KB |
Output is correct |
16 |
Correct |
5 ms |
18780 KB |
Output is correct |
17 |
Correct |
5 ms |
18780 KB |
Output is correct |
18 |
Correct |
6 ms |
18780 KB |
Output is correct |
19 |
Correct |
5 ms |
18780 KB |
Output is correct |
20 |
Correct |
6 ms |
18780 KB |
Output is correct |
21 |
Correct |
5 ms |
18780 KB |
Output is correct |
22 |
Correct |
6 ms |
19032 KB |
Output is correct |
23 |
Correct |
6 ms |
18780 KB |
Output is correct |
24 |
Correct |
6 ms |
19032 KB |
Output is correct |
25 |
Correct |
6 ms |
18780 KB |
Output is correct |
26 |
Correct |
6 ms |
18780 KB |
Output is correct |
27 |
Correct |
5 ms |
18776 KB |
Output is correct |
28 |
Correct |
5 ms |
18780 KB |
Output is correct |
29 |
Correct |
7 ms |
18876 KB |
Output is correct |
30 |
Correct |
7 ms |
18764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
338 ms |
47184 KB |
Output is correct |
2 |
Correct |
152 ms |
47688 KB |
Output is correct |
3 |
Correct |
379 ms |
47080 KB |
Output is correct |
4 |
Correct |
151 ms |
48272 KB |
Output is correct |
5 |
Correct |
337 ms |
44368 KB |
Output is correct |
6 |
Correct |
153 ms |
47956 KB |
Output is correct |
7 |
Correct |
323 ms |
44580 KB |
Output is correct |
8 |
Correct |
153 ms |
47568 KB |
Output is correct |
9 |
Correct |
395 ms |
43040 KB |
Output is correct |
10 |
Correct |
344 ms |
40276 KB |
Output is correct |
11 |
Correct |
407 ms |
46928 KB |
Output is correct |
12 |
Correct |
382 ms |
49560 KB |
Output is correct |
13 |
Correct |
377 ms |
43608 KB |
Output is correct |
14 |
Correct |
383 ms |
49684 KB |
Output is correct |
15 |
Correct |
393 ms |
49676 KB |
Output is correct |
16 |
Correct |
407 ms |
44408 KB |
Output is correct |
17 |
Correct |
399 ms |
44924 KB |
Output is correct |
18 |
Correct |
386 ms |
45076 KB |
Output is correct |
19 |
Correct |
383 ms |
48320 KB |
Output is correct |
20 |
Correct |
383 ms |
50676 KB |
Output is correct |
21 |
Correct |
5 ms |
18780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
18524 KB |
Output is correct |
2 |
Correct |
5 ms |
18780 KB |
Output is correct |
3 |
Correct |
4 ms |
18524 KB |
Output is correct |
4 |
Correct |
4 ms |
18524 KB |
Output is correct |
5 |
Correct |
4 ms |
18524 KB |
Output is correct |
6 |
Correct |
4 ms |
18524 KB |
Output is correct |
7 |
Correct |
5 ms |
18524 KB |
Output is correct |
8 |
Correct |
4 ms |
18524 KB |
Output is correct |
9 |
Correct |
5 ms |
18520 KB |
Output is correct |
10 |
Correct |
4 ms |
18524 KB |
Output is correct |
11 |
Correct |
5 ms |
18624 KB |
Output is correct |
12 |
Correct |
5 ms |
18780 KB |
Output is correct |
13 |
Correct |
7 ms |
18780 KB |
Output is correct |
14 |
Correct |
5 ms |
18780 KB |
Output is correct |
15 |
Correct |
5 ms |
18776 KB |
Output is correct |
16 |
Correct |
5 ms |
18780 KB |
Output is correct |
17 |
Correct |
5 ms |
18780 KB |
Output is correct |
18 |
Correct |
6 ms |
18780 KB |
Output is correct |
19 |
Correct |
5 ms |
18780 KB |
Output is correct |
20 |
Correct |
6 ms |
18780 KB |
Output is correct |
21 |
Correct |
5 ms |
18780 KB |
Output is correct |
22 |
Correct |
6 ms |
19032 KB |
Output is correct |
23 |
Correct |
6 ms |
18780 KB |
Output is correct |
24 |
Correct |
6 ms |
19032 KB |
Output is correct |
25 |
Correct |
6 ms |
18780 KB |
Output is correct |
26 |
Correct |
6 ms |
18780 KB |
Output is correct |
27 |
Correct |
5 ms |
18776 KB |
Output is correct |
28 |
Correct |
5 ms |
18780 KB |
Output is correct |
29 |
Correct |
7 ms |
18876 KB |
Output is correct |
30 |
Correct |
7 ms |
18764 KB |
Output is correct |
31 |
Correct |
338 ms |
47184 KB |
Output is correct |
32 |
Correct |
152 ms |
47688 KB |
Output is correct |
33 |
Correct |
379 ms |
47080 KB |
Output is correct |
34 |
Correct |
151 ms |
48272 KB |
Output is correct |
35 |
Correct |
337 ms |
44368 KB |
Output is correct |
36 |
Correct |
153 ms |
47956 KB |
Output is correct |
37 |
Correct |
323 ms |
44580 KB |
Output is correct |
38 |
Correct |
153 ms |
47568 KB |
Output is correct |
39 |
Correct |
395 ms |
43040 KB |
Output is correct |
40 |
Correct |
344 ms |
40276 KB |
Output is correct |
41 |
Correct |
407 ms |
46928 KB |
Output is correct |
42 |
Correct |
382 ms |
49560 KB |
Output is correct |
43 |
Correct |
377 ms |
43608 KB |
Output is correct |
44 |
Correct |
383 ms |
49684 KB |
Output is correct |
45 |
Correct |
393 ms |
49676 KB |
Output is correct |
46 |
Correct |
407 ms |
44408 KB |
Output is correct |
47 |
Correct |
399 ms |
44924 KB |
Output is correct |
48 |
Correct |
386 ms |
45076 KB |
Output is correct |
49 |
Correct |
383 ms |
48320 KB |
Output is correct |
50 |
Correct |
383 ms |
50676 KB |
Output is correct |
51 |
Correct |
5 ms |
18780 KB |
Output is correct |
52 |
Correct |
275 ms |
32848 KB |
Output is correct |
53 |
Correct |
271 ms |
33016 KB |
Output is correct |
54 |
Correct |
335 ms |
33072 KB |
Output is correct |
55 |
Correct |
282 ms |
33076 KB |
Output is correct |
56 |
Correct |
326 ms |
33128 KB |
Output is correct |
57 |
Correct |
264 ms |
32848 KB |
Output is correct |
58 |
Correct |
237 ms |
36944 KB |
Output is correct |
59 |
Correct |
237 ms |
37368 KB |
Output is correct |
60 |
Correct |
327 ms |
35968 KB |
Output is correct |
61 |
Correct |
387 ms |
35764 KB |
Output is correct |
62 |
Correct |
156 ms |
51516 KB |
Output is correct |
63 |
Correct |
162 ms |
51540 KB |
Output is correct |
64 |
Correct |
156 ms |
51360 KB |
Output is correct |
65 |
Correct |
169 ms |
51560 KB |
Output is correct |
66 |
Correct |
272 ms |
41284 KB |
Output is correct |
67 |
Correct |
237 ms |
41172 KB |
Output is correct |
68 |
Correct |
230 ms |
41428 KB |
Output is correct |
69 |
Correct |
246 ms |
41440 KB |
Output is correct |
70 |
Correct |
309 ms |
41460 KB |
Output is correct |
71 |
Correct |
253 ms |
41292 KB |
Output is correct |
72 |
Correct |
286 ms |
41232 KB |
Output is correct |
73 |
Correct |
234 ms |
40348 KB |
Output is correct |
74 |
Correct |
206 ms |
41492 KB |
Output is correct |
75 |
Correct |
210 ms |
41292 KB |
Output is correct |
76 |
Correct |
331 ms |
40732 KB |
Output is correct |
77 |
Correct |
269 ms |
38992 KB |
Output is correct |
78 |
Correct |
389 ms |
45144 KB |
Output is correct |
79 |
Correct |
362 ms |
42840 KB |
Output is correct |
80 |
Correct |
408 ms |
50160 KB |
Output is correct |
81 |
Correct |
394 ms |
46420 KB |
Output is correct |
82 |
Correct |
390 ms |
46592 KB |
Output is correct |
83 |
Correct |
359 ms |
43380 KB |
Output is correct |
84 |
Correct |
375 ms |
49232 KB |
Output is correct |
85 |
Correct |
446 ms |
47700 KB |
Output is correct |
86 |
Correct |
395 ms |
42996 KB |
Output is correct |
87 |
Correct |
421 ms |
44776 KB |
Output is correct |
88 |
Correct |
313 ms |
44848 KB |
Output is correct |
89 |
Correct |
342 ms |
40820 KB |
Output is correct |
90 |
Correct |
322 ms |
40528 KB |
Output is correct |
91 |
Correct |
311 ms |
43000 KB |
Output is correct |
92 |
Correct |
320 ms |
41520 KB |
Output is correct |
93 |
Correct |
308 ms |
41328 KB |
Output is correct |
94 |
Correct |
332 ms |
40624 KB |
Output is correct |
95 |
Correct |
377 ms |
42040 KB |
Output is correct |
96 |
Correct |
336 ms |
40912 KB |
Output is correct |
97 |
Correct |
418 ms |
42840 KB |
Output is correct |