/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
int n, k, c[maxn];
vector < int > adj[maxn];
vector < int > col[maxn];
void input()
{
cin >> n >> k;
for (int i = 1; i < n; i ++)
{
int v, u;
cin >> v >> u;
///cout << "edge " << v << " " << u << endl;
adj[v].push_back(u);
adj[u].push_back(v);
}
for (int i = 1; i <= n; i ++)
cin >> c[i], col[c[i]].push_back(i);
}
int sub[maxn], par[maxn], last[maxn], used[maxn];
int timer;
void calc(int v, int p)
{
//cout << "calc " << v << " " << p << endl;
last[v] = timer;
par[v] = p;
sub[v] = 1;
for (int u : adj[v])
{
//cout << "neib " << v << " " << u << endl;
if (used[u] || u == p)
continue;
calc(u, v);
sub[v] += sub[u];
}
}
int find_centroid(int v, int p, int sz)
{
for (int u : adj[v])
{
if (u == p || used[u])
continue;
if (sub[u] >= sz / 2)
return find_centroid(u, v, sz);
}
return v;
}
int ans, mark[maxn];
void make_tree(int v)
{
/**cout << "make tree" << endl;
for (int i = 1; i <= n; i ++)
cout << last[i] << " ";
cout << endl;*/
vector < int > cs;
/**for (int i = 1; i <= k; i ++)
mark[i] = 0;*/
queue < int > q;
for (int cur : col[c[v]])
{
if (last[cur] != timer)
return;
q.push(cur);
}
mark[c[v]] = 1;
cs.push_back(c[v]);
int cnt = 0;
while(!q.empty())
{
int cur = q.front();
q.pop();
///cout << "queue " << cur << endl;
if (par[cur] != -1 && !mark[c[par[cur]]])
{
cnt ++;
mark[c[par[cur]]] = 1;
cs.push_back(c[par[cur]]);
for (int ver : col[c[par[cur]]])
{
if (last[ver] != timer)
{
for (int ps : cs)
mark[ps] = 0;
return;
}
q.push(ver);
}
}
}
///cout << cnt << endl;
ans = min(ans, cnt);
for (int ps : cs)
mark[ps] = 0;
///exit(0);
}
void decompose(int v)
{
timer ++;
calc(v, -1);
int centroid = find_centroid(v, -1, sub[v]);
calc(centroid, -1);
///cout << "centroid " << centroid << endl;
make_tree(centroid);
used[centroid] = 1;
for (int u : adj[centroid])
{
if (!used[u])
decompose(u);
}
}
void solve()
{
input();
ans = n;
decompose(1);
cout << ans << endl;
}
int main()
{
speed();
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13404 KB |
Output is correct |
2 |
Correct |
2 ms |
13492 KB |
Output is correct |
3 |
Correct |
2 ms |
13404 KB |
Output is correct |
4 |
Correct |
3 ms |
13404 KB |
Output is correct |
5 |
Correct |
3 ms |
13556 KB |
Output is correct |
6 |
Correct |
3 ms |
13404 KB |
Output is correct |
7 |
Correct |
3 ms |
13404 KB |
Output is correct |
8 |
Correct |
2 ms |
13404 KB |
Output is correct |
9 |
Correct |
3 ms |
13404 KB |
Output is correct |
10 |
Correct |
2 ms |
13404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13404 KB |
Output is correct |
2 |
Correct |
2 ms |
13492 KB |
Output is correct |
3 |
Correct |
2 ms |
13404 KB |
Output is correct |
4 |
Correct |
3 ms |
13404 KB |
Output is correct |
5 |
Correct |
3 ms |
13556 KB |
Output is correct |
6 |
Correct |
3 ms |
13404 KB |
Output is correct |
7 |
Correct |
3 ms |
13404 KB |
Output is correct |
8 |
Correct |
2 ms |
13404 KB |
Output is correct |
9 |
Correct |
3 ms |
13404 KB |
Output is correct |
10 |
Correct |
2 ms |
13404 KB |
Output is correct |
11 |
Correct |
4 ms |
13692 KB |
Output is correct |
12 |
Correct |
4 ms |
13660 KB |
Output is correct |
13 |
Correct |
5 ms |
13660 KB |
Output is correct |
14 |
Correct |
4 ms |
13692 KB |
Output is correct |
15 |
Correct |
4 ms |
13660 KB |
Output is correct |
16 |
Correct |
4 ms |
13660 KB |
Output is correct |
17 |
Correct |
5 ms |
13916 KB |
Output is correct |
18 |
Correct |
3 ms |
13660 KB |
Output is correct |
19 |
Correct |
3 ms |
13660 KB |
Output is correct |
20 |
Correct |
3 ms |
13660 KB |
Output is correct |
21 |
Correct |
3 ms |
13660 KB |
Output is correct |
22 |
Correct |
4 ms |
13660 KB |
Output is correct |
23 |
Correct |
4 ms |
13656 KB |
Output is correct |
24 |
Correct |
4 ms |
13656 KB |
Output is correct |
25 |
Correct |
4 ms |
13660 KB |
Output is correct |
26 |
Correct |
4 ms |
13692 KB |
Output is correct |
27 |
Correct |
4 ms |
13552 KB |
Output is correct |
28 |
Correct |
4 ms |
13660 KB |
Output is correct |
29 |
Correct |
4 ms |
13660 KB |
Output is correct |
30 |
Correct |
4 ms |
13660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
335 ms |
38888 KB |
Output is correct |
2 |
Correct |
135 ms |
43052 KB |
Output is correct |
3 |
Correct |
308 ms |
42224 KB |
Output is correct |
4 |
Correct |
140 ms |
43060 KB |
Output is correct |
5 |
Correct |
319 ms |
39512 KB |
Output is correct |
6 |
Correct |
140 ms |
43040 KB |
Output is correct |
7 |
Correct |
314 ms |
39912 KB |
Output is correct |
8 |
Correct |
138 ms |
42752 KB |
Output is correct |
9 |
Correct |
430 ms |
38176 KB |
Output is correct |
10 |
Correct |
400 ms |
35752 KB |
Output is correct |
11 |
Correct |
343 ms |
38708 KB |
Output is correct |
12 |
Correct |
341 ms |
41272 KB |
Output is correct |
13 |
Correct |
388 ms |
35668 KB |
Output is correct |
14 |
Correct |
359 ms |
41596 KB |
Output is correct |
15 |
Correct |
358 ms |
41172 KB |
Output is correct |
16 |
Correct |
432 ms |
36356 KB |
Output is correct |
17 |
Correct |
486 ms |
36860 KB |
Output is correct |
18 |
Correct |
364 ms |
37040 KB |
Output is correct |
19 |
Correct |
364 ms |
40152 KB |
Output is correct |
20 |
Correct |
424 ms |
42544 KB |
Output is correct |
21 |
Correct |
3 ms |
13404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13404 KB |
Output is correct |
2 |
Correct |
2 ms |
13492 KB |
Output is correct |
3 |
Correct |
2 ms |
13404 KB |
Output is correct |
4 |
Correct |
3 ms |
13404 KB |
Output is correct |
5 |
Correct |
3 ms |
13556 KB |
Output is correct |
6 |
Correct |
3 ms |
13404 KB |
Output is correct |
7 |
Correct |
3 ms |
13404 KB |
Output is correct |
8 |
Correct |
2 ms |
13404 KB |
Output is correct |
9 |
Correct |
3 ms |
13404 KB |
Output is correct |
10 |
Correct |
2 ms |
13404 KB |
Output is correct |
11 |
Correct |
4 ms |
13692 KB |
Output is correct |
12 |
Correct |
4 ms |
13660 KB |
Output is correct |
13 |
Correct |
5 ms |
13660 KB |
Output is correct |
14 |
Correct |
4 ms |
13692 KB |
Output is correct |
15 |
Correct |
4 ms |
13660 KB |
Output is correct |
16 |
Correct |
4 ms |
13660 KB |
Output is correct |
17 |
Correct |
5 ms |
13916 KB |
Output is correct |
18 |
Correct |
3 ms |
13660 KB |
Output is correct |
19 |
Correct |
3 ms |
13660 KB |
Output is correct |
20 |
Correct |
3 ms |
13660 KB |
Output is correct |
21 |
Correct |
3 ms |
13660 KB |
Output is correct |
22 |
Correct |
4 ms |
13660 KB |
Output is correct |
23 |
Correct |
4 ms |
13656 KB |
Output is correct |
24 |
Correct |
4 ms |
13656 KB |
Output is correct |
25 |
Correct |
4 ms |
13660 KB |
Output is correct |
26 |
Correct |
4 ms |
13692 KB |
Output is correct |
27 |
Correct |
4 ms |
13552 KB |
Output is correct |
28 |
Correct |
4 ms |
13660 KB |
Output is correct |
29 |
Correct |
4 ms |
13660 KB |
Output is correct |
30 |
Correct |
4 ms |
13660 KB |
Output is correct |
31 |
Correct |
335 ms |
38888 KB |
Output is correct |
32 |
Correct |
135 ms |
43052 KB |
Output is correct |
33 |
Correct |
308 ms |
42224 KB |
Output is correct |
34 |
Correct |
140 ms |
43060 KB |
Output is correct |
35 |
Correct |
319 ms |
39512 KB |
Output is correct |
36 |
Correct |
140 ms |
43040 KB |
Output is correct |
37 |
Correct |
314 ms |
39912 KB |
Output is correct |
38 |
Correct |
138 ms |
42752 KB |
Output is correct |
39 |
Correct |
430 ms |
38176 KB |
Output is correct |
40 |
Correct |
400 ms |
35752 KB |
Output is correct |
41 |
Correct |
343 ms |
38708 KB |
Output is correct |
42 |
Correct |
341 ms |
41272 KB |
Output is correct |
43 |
Correct |
388 ms |
35668 KB |
Output is correct |
44 |
Correct |
359 ms |
41596 KB |
Output is correct |
45 |
Correct |
358 ms |
41172 KB |
Output is correct |
46 |
Correct |
432 ms |
36356 KB |
Output is correct |
47 |
Correct |
486 ms |
36860 KB |
Output is correct |
48 |
Correct |
364 ms |
37040 KB |
Output is correct |
49 |
Correct |
364 ms |
40152 KB |
Output is correct |
50 |
Correct |
424 ms |
42544 KB |
Output is correct |
51 |
Correct |
3 ms |
13404 KB |
Output is correct |
52 |
Correct |
212 ms |
26608 KB |
Output is correct |
53 |
Correct |
244 ms |
26500 KB |
Output is correct |
54 |
Correct |
272 ms |
26452 KB |
Output is correct |
55 |
Correct |
221 ms |
26448 KB |
Output is correct |
56 |
Correct |
231 ms |
26612 KB |
Output is correct |
57 |
Correct |
221 ms |
26620 KB |
Output is correct |
58 |
Correct |
237 ms |
29692 KB |
Output is correct |
59 |
Correct |
228 ms |
30196 KB |
Output is correct |
60 |
Correct |
299 ms |
29400 KB |
Output is correct |
61 |
Correct |
257 ms |
29004 KB |
Output is correct |
62 |
Correct |
150 ms |
42836 KB |
Output is correct |
63 |
Correct |
144 ms |
42832 KB |
Output is correct |
64 |
Correct |
150 ms |
42948 KB |
Output is correct |
65 |
Correct |
142 ms |
43068 KB |
Output is correct |
66 |
Correct |
197 ms |
34984 KB |
Output is correct |
67 |
Correct |
222 ms |
34812 KB |
Output is correct |
68 |
Correct |
207 ms |
34944 KB |
Output is correct |
69 |
Correct |
185 ms |
34760 KB |
Output is correct |
70 |
Correct |
195 ms |
34860 KB |
Output is correct |
71 |
Correct |
210 ms |
34856 KB |
Output is correct |
72 |
Correct |
189 ms |
34760 KB |
Output is correct |
73 |
Correct |
189 ms |
33996 KB |
Output is correct |
74 |
Correct |
201 ms |
35020 KB |
Output is correct |
75 |
Correct |
205 ms |
34920 KB |
Output is correct |
76 |
Correct |
274 ms |
33492 KB |
Output is correct |
77 |
Correct |
282 ms |
31648 KB |
Output is correct |
78 |
Correct |
376 ms |
36748 KB |
Output is correct |
79 |
Correct |
394 ms |
34776 KB |
Output is correct |
80 |
Correct |
370 ms |
41964 KB |
Output is correct |
81 |
Correct |
374 ms |
38484 KB |
Output is correct |
82 |
Correct |
384 ms |
38588 KB |
Output is correct |
83 |
Correct |
366 ms |
35192 KB |
Output is correct |
84 |
Correct |
374 ms |
41056 KB |
Output is correct |
85 |
Correct |
356 ms |
39456 KB |
Output is correct |
86 |
Correct |
353 ms |
34800 KB |
Output is correct |
87 |
Correct |
387 ms |
36692 KB |
Output is correct |
88 |
Correct |
294 ms |
37396 KB |
Output is correct |
89 |
Correct |
313 ms |
33800 KB |
Output is correct |
90 |
Correct |
291 ms |
33484 KB |
Output is correct |
91 |
Correct |
325 ms |
35668 KB |
Output is correct |
92 |
Correct |
296 ms |
34424 KB |
Output is correct |
93 |
Correct |
316 ms |
34192 KB |
Output is correct |
94 |
Correct |
292 ms |
33364 KB |
Output is correct |
95 |
Correct |
323 ms |
34884 KB |
Output is correct |
96 |
Correct |
313 ms |
33772 KB |
Output is correct |
97 |
Correct |
330 ms |
35652 KB |
Output is correct |