#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=200010, LOG=20;
int n, m, k, u, v, x, y, t, a, b, ans=inf, shit;
int C[MAXN], mark2[MAXN], mark3[MAXN], ted[MAXN];
bool dead[MAXN], dead2[MAXN], mark[MAXN];
int par[MAXN], sz[MAXN];
vector<int> G[MAXN], V[MAXN];
int dfs1(int node, int par){
sz[node]=1;
for (int v:G[node]) if (v!=par && !dead[v]) sz[node]+=dfs1(v, node);
return sz[node];
}
int Centroid(int node, int par, int n){
for (int v:G[node]) if (v!=par && !dead[v] && sz[v]*2>n) return Centroid(v, node, n);
return node;
}
inline void addc(int c){
if (mark2[c]==shit) ted[c]++;
else mark2[c]=shit, ted[c]=1;
}
void dfs2(int node){
mark[node]=0;
addc(C[node]);
for (int v:G[node]) if (v!=par[node] && !dead[v]){
par[v]=node;
dfs2(v);
}
}
void Decompose(int root){
root=Centroid(root, root, dfs1(root, root));
// debug(root)
shit++;
if (!dead2[C[root]]){
dead2[C[root]]=1;
par[root]=0;
dfs2(root);
vector<int> vec={C[root]};
mark3[C[root]]=shit;
int res=0, bad=0;
while (vec.size() && !bad){
int c=vec.back();
vec.pop_back();
if (V[c].size()!=ted[c] || dead2[c]){
bad=1;
break ;
}
// debug(c)
res++;
for (int v:V[c]){
while (v && !mark[v]){
if (mark3[C[v]]!=shit){
int cc=C[v];
vec.pb(cc);
mark3[cc]=shit;
}
v=par[v];
}
if (bad) break ;
}
}
if (!bad) ans=min(ans, res);
}
dead[root]=1;
for (int v:G[root]) if (!dead[v]) Decompose(v);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>k;
for (int i=1; i<n; i++){
cin>>u>>v;
G[u].pb(v);
G[v].pb(u);
}
for (int i=1; i<=n; i++) cin>>C[i], V[C[i]].pb(i);
Decompose(1);
cout<<ans-1<<"\n";
return 0;
}
Compilation message
capital_city.cpp: In function 'void Decompose(int)':
capital_city.cpp:66:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
66 | if (V[c].size()!=ted[c] || dead2[c]){
| ~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
540 ms |
38508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
