#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) {
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
18524 KB |
Output is correct |
2 |
Correct |
4 ms |
18672 KB |
Output is correct |
3 |
Correct |
4 ms |
18524 KB |
Output is correct |
4 |
Correct |
5 ms |
18524 KB |
Output is correct |
5 |
Correct |
5 ms |
18676 KB |
Output is correct |
6 |
Correct |
4 ms |
18520 KB |
Output is correct |
7 |
Correct |
4 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 |
18520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
18524 KB |
Output is correct |
2 |
Correct |
4 ms |
18672 KB |
Output is correct |
3 |
Correct |
4 ms |
18524 KB |
Output is correct |
4 |
Correct |
5 ms |
18524 KB |
Output is correct |
5 |
Correct |
5 ms |
18676 KB |
Output is correct |
6 |
Correct |
4 ms |
18520 KB |
Output is correct |
7 |
Correct |
4 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 |
18520 KB |
Output is correct |
11 |
Correct |
5 ms |
18776 KB |
Output is correct |
12 |
Correct |
5 ms |
18780 KB |
Output is correct |
13 |
Correct |
5 ms |
18780 KB |
Output is correct |
14 |
Correct |
5 ms |
18776 KB |
Output is correct |
15 |
Correct |
5 ms |
18684 KB |
Output is correct |
16 |
Correct |
5 ms |
18712 KB |
Output is correct |
17 |
Correct |
5 ms |
18780 KB |
Output is correct |
18 |
Incorrect |
5 ms |
18780 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
344 ms |
51148 KB |
Output is correct |
2 |
Correct |
180 ms |
51540 KB |
Output is correct |
3 |
Correct |
322 ms |
50516 KB |
Output is correct |
4 |
Correct |
148 ms |
51436 KB |
Output is correct |
5 |
Correct |
341 ms |
47696 KB |
Output is correct |
6 |
Correct |
176 ms |
51536 KB |
Output is correct |
7 |
Correct |
323 ms |
48204 KB |
Output is correct |
8 |
Correct |
153 ms |
51364 KB |
Output is correct |
9 |
Correct |
397 ms |
46572 KB |
Output is correct |
10 |
Incorrect |
356 ms |
43896 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
18524 KB |
Output is correct |
2 |
Correct |
4 ms |
18672 KB |
Output is correct |
3 |
Correct |
4 ms |
18524 KB |
Output is correct |
4 |
Correct |
5 ms |
18524 KB |
Output is correct |
5 |
Correct |
5 ms |
18676 KB |
Output is correct |
6 |
Correct |
4 ms |
18520 KB |
Output is correct |
7 |
Correct |
4 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 |
18520 KB |
Output is correct |
11 |
Correct |
5 ms |
18776 KB |
Output is correct |
12 |
Correct |
5 ms |
18780 KB |
Output is correct |
13 |
Correct |
5 ms |
18780 KB |
Output is correct |
14 |
Correct |
5 ms |
18776 KB |
Output is correct |
15 |
Correct |
5 ms |
18684 KB |
Output is correct |
16 |
Correct |
5 ms |
18712 KB |
Output is correct |
17 |
Correct |
5 ms |
18780 KB |
Output is correct |
18 |
Incorrect |
5 ms |
18780 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |