#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 findcen( int u, int p, int all, pii &ret ) {
//printf("cen : %d\n",u);
int mx = all - sz[u];
for( int v : g[u] ) if( v != p && !chk[v] )
mx = max( mx, findcen( v, u, all, ret ) );
ret = min( ret, pii( mx, 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], ret );
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",ans-1);
return 0;
}
Compilation message
capital_city.cpp: In function 'void centroid(int)':
capital_city.cpp:44: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:63: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:65: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:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&c[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
978 ms |
37600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
