#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <cassert>
#include <random>
#include <chrono>
#include <unordered_set>
#include <unordered_map>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using ull = unsigned long long;
using ll = long long;
//#define int __int128
//#define int ll
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define fr first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define vt vector
#define FOR(a, b) for(int i = (a); i <= (b); i++)
#define FORr(a, b) for(int i = (a); i >= (b); i--)
#define sz(x) (int)(x).size()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rangerng(int l, int r){
return uniform_int_distribution<>(l, r)(rng);
}
////////////////////////////////////////////////////////////////////////////////////
const int NMAX = 2e5;
int c[NMAX + 1];
vt <int> adj[NMAX + 1];
int sz[NMAX + 1];
bool proc[NMAX + 1];
int f[NMAX + 1];
void recalc_sz(int node, int par){
sz[node] = 1;
for(int child : adj[node]){
if(!proc[child] && child != par){
recalc_sz(child, node);
sz[node] += sz[child];
}
}
}
int get_centroid(int node, int par, int lim){
for(int child : adj[node]){
if(!proc[child] && child != par && sz[child] > lim){
return get_centroid(child, node, lim);
}
}
return node;
}
int parent[NMAX + 1];
vt <int> inds[NMAX + 1];
void dfs(int node, int par){
parent[node] = par;
inds[c[node]].clear();
for(int vec : adj[node]){
if(!proc[vec] && vec != par){
dfs(vec, node);
}
}
}
void dfs2(int node, int par){
inds[c[node]].pb(node);
for(int vec : adj[node]){
if(!proc[vec] && vec != par){
dfs2(vec, node);
}
}
}
int mini = 1e9;
void decomp(int node){
recalc_sz(node, 0);
int centroid = get_centroid(node, 0, sz[node] / 2);
proc[centroid] = true;
dfs(centroid, 0);
dfs2(centroid, 0);
queue <int> Q;
unordered_set <int> S;
Q.push(c[centroid]);
S.insert(c[centroid]);
int adds = 1;
bool ok = 1;
while(!Q.empty()){
int col = Q.front();
Q.pop();
if(f[col] != sz(inds[col])){
ok = 0;
}
for(int node : inds[col]){
if(node != centroid && S.find(c[parent[node]]) == S.end()){
S.insert(c[parent[node]]);
Q.push(c[parent[node]]);
adds++;
}
}
}
if(ok){
mini = min(mini, adds - 1);
}
for(int vec : adj[centroid]){
if(!proc[vec]){
decomp(vec);
}
}
}
void solve(){
int n, k;
cin >> n >> k;
FOR(1, n - 1){
int a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
FOR(1, n){
cin >> c[i];
f[c[i]]++;
}
decomp(1);
cout << mini << endl;
}
signed main(){
//ios_base::sync_with_stdio(false);
//cin.tie(0);
int T;
//cin >> T;
T = 1;
while(T--){
solve();
}
return 0;
}
/*
12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
3 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
3 ms |
12892 KB |
Output is correct |
6 |
Correct |
3 ms |
12892 KB |
Output is correct |
7 |
Correct |
3 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
3 ms |
12888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
3 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
3 ms |
12892 KB |
Output is correct |
6 |
Correct |
3 ms |
12892 KB |
Output is correct |
7 |
Correct |
3 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
3 ms |
12888 KB |
Output is correct |
11 |
Correct |
5 ms |
12892 KB |
Output is correct |
12 |
Correct |
5 ms |
12892 KB |
Output is correct |
13 |
Correct |
7 ms |
12892 KB |
Output is correct |
14 |
Correct |
5 ms |
12892 KB |
Output is correct |
15 |
Correct |
5 ms |
12892 KB |
Output is correct |
16 |
Correct |
5 ms |
12888 KB |
Output is correct |
17 |
Correct |
5 ms |
12888 KB |
Output is correct |
18 |
Correct |
5 ms |
12892 KB |
Output is correct |
19 |
Correct |
5 ms |
12892 KB |
Output is correct |
20 |
Correct |
5 ms |
12892 KB |
Output is correct |
21 |
Correct |
4 ms |
12892 KB |
Output is correct |
22 |
Correct |
5 ms |
13148 KB |
Output is correct |
23 |
Correct |
5 ms |
12892 KB |
Output is correct |
24 |
Correct |
5 ms |
12892 KB |
Output is correct |
25 |
Correct |
6 ms |
13144 KB |
Output is correct |
26 |
Correct |
8 ms |
13196 KB |
Output is correct |
27 |
Correct |
6 ms |
13148 KB |
Output is correct |
28 |
Correct |
6 ms |
13144 KB |
Output is correct |
29 |
Correct |
7 ms |
12888 KB |
Output is correct |
30 |
Correct |
5 ms |
12892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
479 ms |
37716 KB |
Output is correct |
2 |
Correct |
257 ms |
38016 KB |
Output is correct |
3 |
Correct |
482 ms |
37376 KB |
Output is correct |
4 |
Correct |
258 ms |
38224 KB |
Output is correct |
5 |
Correct |
506 ms |
34984 KB |
Output is correct |
6 |
Correct |
259 ms |
41884 KB |
Output is correct |
7 |
Correct |
545 ms |
39732 KB |
Output is correct |
8 |
Correct |
263 ms |
42704 KB |
Output is correct |
9 |
Correct |
628 ms |
39688 KB |
Output is correct |
10 |
Correct |
642 ms |
37600 KB |
Output is correct |
11 |
Correct |
710 ms |
40380 KB |
Output is correct |
12 |
Correct |
707 ms |
42936 KB |
Output is correct |
13 |
Correct |
695 ms |
37024 KB |
Output is correct |
14 |
Correct |
617 ms |
43184 KB |
Output is correct |
15 |
Correct |
632 ms |
43172 KB |
Output is correct |
16 |
Correct |
711 ms |
38128 KB |
Output is correct |
17 |
Correct |
718 ms |
38652 KB |
Output is correct |
18 |
Correct |
634 ms |
38728 KB |
Output is correct |
19 |
Correct |
652 ms |
41904 KB |
Output is correct |
20 |
Correct |
696 ms |
44008 KB |
Output is correct |
21 |
Correct |
3 ms |
12892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
12892 KB |
Output is correct |
2 |
Correct |
3 ms |
12892 KB |
Output is correct |
3 |
Correct |
3 ms |
12892 KB |
Output is correct |
4 |
Correct |
3 ms |
12892 KB |
Output is correct |
5 |
Correct |
3 ms |
12892 KB |
Output is correct |
6 |
Correct |
3 ms |
12892 KB |
Output is correct |
7 |
Correct |
3 ms |
12892 KB |
Output is correct |
8 |
Correct |
3 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
3 ms |
12888 KB |
Output is correct |
11 |
Correct |
5 ms |
12892 KB |
Output is correct |
12 |
Correct |
5 ms |
12892 KB |
Output is correct |
13 |
Correct |
7 ms |
12892 KB |
Output is correct |
14 |
Correct |
5 ms |
12892 KB |
Output is correct |
15 |
Correct |
5 ms |
12892 KB |
Output is correct |
16 |
Correct |
5 ms |
12888 KB |
Output is correct |
17 |
Correct |
5 ms |
12888 KB |
Output is correct |
18 |
Correct |
5 ms |
12892 KB |
Output is correct |
19 |
Correct |
5 ms |
12892 KB |
Output is correct |
20 |
Correct |
5 ms |
12892 KB |
Output is correct |
21 |
Correct |
4 ms |
12892 KB |
Output is correct |
22 |
Correct |
5 ms |
13148 KB |
Output is correct |
23 |
Correct |
5 ms |
12892 KB |
Output is correct |
24 |
Correct |
5 ms |
12892 KB |
Output is correct |
25 |
Correct |
6 ms |
13144 KB |
Output is correct |
26 |
Correct |
8 ms |
13196 KB |
Output is correct |
27 |
Correct |
6 ms |
13148 KB |
Output is correct |
28 |
Correct |
6 ms |
13144 KB |
Output is correct |
29 |
Correct |
7 ms |
12888 KB |
Output is correct |
30 |
Correct |
5 ms |
12892 KB |
Output is correct |
31 |
Correct |
479 ms |
37716 KB |
Output is correct |
32 |
Correct |
257 ms |
38016 KB |
Output is correct |
33 |
Correct |
482 ms |
37376 KB |
Output is correct |
34 |
Correct |
258 ms |
38224 KB |
Output is correct |
35 |
Correct |
506 ms |
34984 KB |
Output is correct |
36 |
Correct |
259 ms |
41884 KB |
Output is correct |
37 |
Correct |
545 ms |
39732 KB |
Output is correct |
38 |
Correct |
263 ms |
42704 KB |
Output is correct |
39 |
Correct |
628 ms |
39688 KB |
Output is correct |
40 |
Correct |
642 ms |
37600 KB |
Output is correct |
41 |
Correct |
710 ms |
40380 KB |
Output is correct |
42 |
Correct |
707 ms |
42936 KB |
Output is correct |
43 |
Correct |
695 ms |
37024 KB |
Output is correct |
44 |
Correct |
617 ms |
43184 KB |
Output is correct |
45 |
Correct |
632 ms |
43172 KB |
Output is correct |
46 |
Correct |
711 ms |
38128 KB |
Output is correct |
47 |
Correct |
718 ms |
38652 KB |
Output is correct |
48 |
Correct |
634 ms |
38728 KB |
Output is correct |
49 |
Correct |
652 ms |
41904 KB |
Output is correct |
50 |
Correct |
696 ms |
44008 KB |
Output is correct |
51 |
Correct |
3 ms |
12892 KB |
Output is correct |
52 |
Correct |
395 ms |
26284 KB |
Output is correct |
53 |
Correct |
430 ms |
26452 KB |
Output is correct |
54 |
Correct |
370 ms |
26372 KB |
Output is correct |
55 |
Correct |
500 ms |
26260 KB |
Output is correct |
56 |
Correct |
478 ms |
26388 KB |
Output is correct |
57 |
Correct |
428 ms |
26580 KB |
Output is correct |
58 |
Correct |
422 ms |
29948 KB |
Output is correct |
59 |
Correct |
369 ms |
29264 KB |
Output is correct |
60 |
Correct |
488 ms |
28224 KB |
Output is correct |
61 |
Correct |
493 ms |
28752 KB |
Output is correct |
62 |
Correct |
270 ms |
41928 KB |
Output is correct |
63 |
Correct |
267 ms |
41812 KB |
Output is correct |
64 |
Correct |
273 ms |
42516 KB |
Output is correct |
65 |
Correct |
264 ms |
41808 KB |
Output is correct |
66 |
Correct |
402 ms |
33484 KB |
Output is correct |
67 |
Correct |
325 ms |
33560 KB |
Output is correct |
68 |
Correct |
335 ms |
33576 KB |
Output is correct |
69 |
Correct |
342 ms |
33708 KB |
Output is correct |
70 |
Correct |
325 ms |
33612 KB |
Output is correct |
71 |
Correct |
364 ms |
33400 KB |
Output is correct |
72 |
Correct |
362 ms |
33484 KB |
Output is correct |
73 |
Correct |
339 ms |
32792 KB |
Output is correct |
74 |
Correct |
400 ms |
33520 KB |
Output is correct |
75 |
Correct |
361 ms |
33612 KB |
Output is correct |
76 |
Correct |
457 ms |
34204 KB |
Output is correct |
77 |
Correct |
409 ms |
32940 KB |
Output is correct |
78 |
Correct |
735 ms |
38496 KB |
Output is correct |
79 |
Correct |
680 ms |
36520 KB |
Output is correct |
80 |
Correct |
656 ms |
43668 KB |
Output is correct |
81 |
Correct |
713 ms |
39984 KB |
Output is correct |
82 |
Correct |
710 ms |
40148 KB |
Output is correct |
83 |
Correct |
644 ms |
36784 KB |
Output is correct |
84 |
Correct |
678 ms |
42864 KB |
Output is correct |
85 |
Correct |
648 ms |
41316 KB |
Output is correct |
86 |
Correct |
659 ms |
36732 KB |
Output is correct |
87 |
Correct |
654 ms |
38312 KB |
Output is correct |
88 |
Correct |
502 ms |
37776 KB |
Output is correct |
89 |
Correct |
531 ms |
33876 KB |
Output is correct |
90 |
Correct |
581 ms |
33560 KB |
Output is correct |
91 |
Correct |
549 ms |
35924 KB |
Output is correct |
92 |
Correct |
570 ms |
34844 KB |
Output is correct |
93 |
Correct |
562 ms |
34356 KB |
Output is correct |
94 |
Correct |
527 ms |
33552 KB |
Output is correct |
95 |
Correct |
598 ms |
35408 KB |
Output is correct |
96 |
Correct |
534 ms |
34024 KB |
Output is correct |
97 |
Correct |
497 ms |
35832 KB |
Output is correct |