#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) begin(a),end(a)
const int mxN = (int)2e5+2;
vector<int> v[mxN];
int n, m, ans = mxN;
int col[mxN], sub[mxN], par[mxN], vis[mxN], vis2[mxN];
vector<int> adj[mxN];
int getSub(int s, int p){
sub[s] = 1; par[s]=p;
for(auto u : adj[s])
if(u!=p and !vis[u]) sub[s]+=getSub(u,s);
return sub[s];
}
int findCen(int s, int p, int n){
for(auto u : adj[s])
if(u!=p and !vis[u] and sub[u]>n/2)
return findCen(u,s,n);
return s;
}
void dfs(int s, int p){
par[s] = p;
for(auto u : adj[s])
if(u!=p and !vis[u]) dfs(u,s);
}
/*
To construct this city, we take all vertices that have the same color as the centroid,
check their parents in the tree, and if the parent has a different color,
we will repeat the same proccess with that color. This can be done efficiently with a queue.
*/
void cenDec(int cen, int p){
cen = findCen(cen,p,getSub(cen,cen));
if(!vis2[col[cen]]){
queue<int> Q = queue<int>(); Q.push(cen);
bool ok = 1; int cnt = 0;
while(!Q.empty() and ok){
auto a = Q.front(); Q.pop(); vis[a]=1;
int C = col[a];
if(!vis2[C]){
for(auto u : v[C]) if(col[par[u]]!=C) Q.push(par[u]);
vis2[C]=1; cnt++;
}
}
if(ok) ans = min(ans, cnt);
}
for(auto u : adj[cen])
if(u!=p and !vis[u]) cenDec(u,cen);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for(int i = 1; i < n; i++){
int a, b; cin >> a >> b;
adj[a].pb(b), adj[b].pb(a);
}
for(int i = 1; i <= n; i++) cin >> col[i], v[col[i]].pb(i);
cenDec(1,-1); cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
171 ms |
34736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
