#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) begin(a),end(a)
const int mxN = (int)1e5+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);
}
/*
Root the tree at the centroid, and keep track of previous centroids
(these vertices will be "blocked" in the tree).
We will consider a city, such that the current centroid is included in this city,
and all "blocked" vertices and vertices below them must not be included.
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.
After this proccess terminates (there are no more colors that we must add),
we will check if none of the added colors have vertices under "blocked" vertices,
and if this is true we will minimize the answer with amountOfColorsAdded−1
.
*/
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 = 1;
while(!Q.empty() and ok){
auto a = Q.front(); Q.pop();
int C = col[par[a]];
if(vis[a]) ok=0;
else if(!vis2[C]){
for(auto u : v[C]) Q.push(u);
vis2[C]=1; cnt++;
}
}
if(ok) ans = min(ans, cnt-1);
}
vis[cen] = 1;
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 |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
17196 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
