#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
int par[N], cc[N], sz[N], c[N], cnt[N], ans = 1e9, n, k;
bool chk[N];
vector<int> col[N], g[N];
queue<int> q;
int getsz( int u, int p ) { sz[u] = 1; for( int v : g[u] ) if( v != p && !chk[v] ) sz[u] += getsz( v, u ); return sz[u]; }
int find_cen(int u, int p, int all, int &ret) {
int mx = all - sz[u];
for(int v : g[u]) if(v != p && !chk[v])
mx = max(mx, find_cen(v, u, all, ret));
if(mx <= (all + 1) / 2) ret = u;
return sz[u];
}
void dfs( int u, int p, bool fill ) {
if( fill ) col[c[u]].emplace_back( u ), par[u] = p;
else col[c[u]].clear(), cc[c[u]] = false;
for( int v : g[u] ) if( v != p && !chk[v] ) dfs( v, u, fill );
}
void centroid( int u ) {
//printf("%d ",u);
// pii ret( 1e9, -1 );
getsz( u, u );
findcen( u, u, sz[u], u );
dfs( u, 0, true );
bool check = true;
u = ret.y;
//printf("CEN : %d\n",u);
int cou = 1;
q.emplace( c[u] ), cc[c[u]] = true;
while( !q.empty() ) {
int now = q.front(); q.pop();
if( col[now].size() != cnt[now] ) {
check = false;
break ;
}
for( int x : col[now] ) if( x != u && !cc[c[par[x]]] ) {
cc[c[par[x]]] = true;
cou++;
q.emplace( c[par[x]] );
}
}
//while( !q.empty() ) q.pop();
if( check ) ans = min( ans, cou );
dfs( u, 0, false ), chk[u] = true;
for( int v : g[u] ) if( !chk[v] ) centroid( v );
}
int main()
{
scanf("%d %d",&n,&k);
for( int i = 1, a, b ; i < n ; i++ ) {
scanf("%d %d",&a,&b);
g[a].emplace_back( b ), g[b].emplace_back( a );
}
for( int i = 1 ; i <= n ; i++ ) {
scanf("%d",&c[i]);
cnt[c[i]]++;
}
centroid( 1 );
printf("%d\n",ans-1);
return 0;
}
Compilation message
capital_city.cpp: In function 'void centroid(int)':
capital_city.cpp:33:5: error: 'findcen' was not declared in this scope
findcen( u, u, sz[u], u );
^~~~~~~
capital_city.cpp:33:5: note: suggested alternative: 'find_cen'
findcen( u, u, sz[u], u );
^~~~~~~
find_cen
capital_city.cpp:36:9: error: 'ret' was not declared in this scope
u = ret.y;
^~~
capital_city.cpp:42:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( col[now].size() != cnt[now] ) {
~~~~~~~~~~~~~~~~^~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:61: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:63: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:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&c[i]);
~~~~~^~~~~~~~~~~~
