#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5;
int n,k,ans=1e9;
bool f[N],fix[N],lvl[N];
int c[N],P[N],Cf[N],F[N];
vector < int > v[N],s[N],h;
int Dfs(int x,int p,int sz,int ¢er) {
int tot=1;
P[x]=p;
Cf[c[x]]++;
h.pb(x);
for (int i=0; i<v[x].size(); i++) {
int to=v[x][i];
if (!lvl[to] && to!=p) tot+=Dfs(to,x,sz,center);
}
if (center==-1 && (2*tot>=sz || !p)) center=x;
return tot;
}
void Build(int x,int sz) {
int center=-1;
Dfs(x,0,sz,center);
queue < int > q;
lvl[center]=1;
q.push(center);
int cn=0;
while (!q.empty()) {
int x=q.front();
q.pop();
if (fix[x]) continue;
fix[x]=1;
if (F[c[x]]!=Cf[c[x]]) {
cn=1e9;
while (!q.empty())
q.pop();
break;
}
if (!f[c[x]]) {
cn++;
f[c[x]]=1;
for (int i=0; i<s[c[x]].size(); i++)
q.push(s[c[x]][i]);
}
if (P[x])
q.push(P[x]);
}
for (int i=0; i<h.size(); i++) {
int x=h[i];
Cf[c[x]]=f[c[x]]=0,fix[x]=0;
}
h.clear();
ans=min(ans,cn);
for (int i=0; i<v[center].size(); i++) {
int to=v[center][i];
if (!lvl[to]) Build(to,sz/2);
}
}
main () {
cin>>n>>k;
for (int i=1; i<n; i++) {
int a,b;
cin>>a>>b;
v[a].pb(b);
v[b].pb(a);
}
for (int i=1; i<=n; i++) {
cin>>c[i];
F[c[i]]++;
s[c[i]].pb(i);
}
Build(1,n);
--ans;
cout<<ans<<endl;
}
Compilation message
capital_city.cpp: In function 'int Dfs(int, int, int, int&)':
capital_city.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++) {
~^~~~~~~~~~~~
capital_city.cpp: In function 'void Build(int, int)':
capital_city.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<s[c[x]].size(); i++)
~^~~~~~~~~~~~~~~
capital_city.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<h.size(); i++) {
~^~~~~~~~~
capital_city.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[center].size(); i++) {
~^~~~~~~~~~~~~~~~~
capital_city.cpp: At global scope:
capital_city.cpp:64:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
10 ms |
9728 KB |
Output is correct |
4 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
10 ms |
9728 KB |
Output is correct |
4 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
666 ms |
35052 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
10 ms |
9728 KB |
Output is correct |
4 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |