#include <bits/stdc++.h>
#define eb emplace_back
const int inf=987654321;
using namespace std;
typedef long long LL;
int n, k, col[200010], siz[200010];
vector<int> link[200010], vcm[200010];
void dfs(int num, int par){
siz[num]=1;
vcm[col[num]].eb(num);
for(auto i:link[num]){
if(i==par)continue;
dfs(i, num);
siz[num]+=siz[i];
}
}
bool ch[200010];
int get_centroid(int num, int par, int sz){
bool flag=true;
for(auto i:link[num]){
if(ch[i])continue;
if(siz[i]>sz/2)flag=false;
}
if(flag)return num;
for(auto i:link[num]){
if(i==par||ch[i])continue;
int temp=siz[i];
siz[num]=sz-siz[i];
siz[i]=sz;
int ret=get_centroid(i, num, sz);
if(ret)return ret;
siz[num]=sz;
siz[i]=temp;
}
return 0;
}
int ans=inf, p[200010], cnt[200010];
vector<int> vc[200010], tmp;
void dfs2(int num, int par){
p[num]=par;
tmp.eb(col[num]);
cnt[col[num]]++;
for(auto i:link[num]){
if(i==par||ch[i])continue;
dfs2(i, num);
}
}
int que[200010], re, fr;
bool ch2[200010];
void make_centroidtree(int num, int par){
int cen=get_centroid(num, 0, siz[num]), ret=0; re=0;
ch[cen]=true;
dfs2(cen, 0);
if(cnt[col[num]]!=vcm[col[cen]].size())ret=inf;
for(auto i:vcm[col[cen]])que[++re]=i;
ch2[col[cen]]=true;
for(fr=1; fr<=re; fr++){
if(ch2[col[p[que[fr]]]])continue;
ch2[col[p[que[fr]]]]=true;
if(cnt[col[num]]!=vcm[col[p[que[fr]]]].size())ret=inf;
for(auto i:vcm[col[p[que[fr]]]])que[++re]=i;
ret++;
}
ans=min(ans, ret);
for(auto i:tmp)ch2[i]=false;
tmp.clear();
for(auto i:link[cen]){
if(!ch[i])make_centroidtree(i, cen);
}
}
int main(){
scanf("%d %d", &n, &k);
ch2[0]=true;
for(int i=1; i<n; i++){
int a, b;
scanf("%d %d", &a, &b);
link[a].eb(b);
link[b].eb(a);
}
for(int i=1; i<=n; i++)scanf("%d", &col[i]);
dfs(1, 0);
make_centroidtree(1, 0);
printf("%d", ans);
}
Compilation message
capital_city.cpp: In function 'void make_centroidtree(int, int)':
capital_city.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cnt[col[num]]!=vcm[col[cen]].size())ret=inf;
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:60:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cnt[col[num]]!=vcm[col[p[que[fr]]]].size())ret=inf;
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:80:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=n; i++)scanf("%d", &col[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
652 ms |
40704 KB |
Output is correct |
| 2 |
Correct |
236 ms |
44524 KB |
Output is correct |
| 3 |
Correct |
632 ms |
43912 KB |
Output is correct |
| 4 |
Correct |
240 ms |
44496 KB |
Output is correct |
| 5 |
Incorrect |
1426 ms |
41440 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
