이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 2e5+5, inf = INT_MAX/4;
int n, k, c[MAXN], ans[MAXN], mark[MAXN], cm = 0, par[MAXN], sz[MAXN], m;
vector <int> adj[MAXN], all[MAXN], clr, clrc;
bool dead[MAXN], visi[MAXN], inc[MAXN];
void dfs(int v, int parv){
m++; sz[v] = 1;
for(int u: adj[v]){
if(!dead[u] && u != parv){
par[u] = v;
dfs(u, v);
sz[v] += sz[u];
}
}
return;
}
inline int findcentroid(int v){
int cent = v; par[v] = -1; m = 0;
dfs(v, -1);
bool f = false;
while(!f){
f = true;
for(int u: adj[cent]){
if(!dead[u] && u != par[cent] && sz[u] >= (m / 2)){
f = false;
cent = u;
break;
}
}
}
return cent;
}
void dfs2(int v, int parv){
mark[v] = cm;
for(int u: adj[v])
if(!dead[u] && u!=parv){
par[u] = v;
dfs2(u,v);
}
return;
}
void calc(int r){
while(!clr.empty()){
visi[clr.back()] = false; clr.pop_back();
}
while(!clrc.empty()){
inc[clrc.back()] = false; clrc.pop_back();
}
queue <int> q;
for(int i: all[c[r]]){
if(mark[i] != cm){
ans[r] = inf;
return;
}
q.push(i);
}
clrc.push_back(c[r]); inc[c[r]] = true;
while(!q.empty()){
int v = q.front(); q.pop();
while(v!=-1 && !visi[v]){
visi[v] = true; clr.push_back(v);
// cout << "v:" << v+1 << " parv:" << par[v]+1 << endl;
if(!inc[c[v]]){
// cout << "IIFFFF " << c[v] << endl;
for(int i: all[c[v]]){
if(mark[i] != cm){
ans[r] = inf;
return;
}
if(i!=v && !visi[i]) q.push(i);
}
clrc.push_back(c[v]); inc[c[v]] = true; ans[r]++;
}
v = par[v];
}
}
return;
}
void slv(int v){
int cent = findcentroid(v);
cm++; par[cent] = -1; dfs2(cent,-1);
calc(cent);
// cout << "cent:" << cent+1 << " ans:" << ans[cent] << endl;
dead[cent] = true;
for(auto u: adj[cent])
if(!dead[u]) slv(u);
return;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 0; i < n-1; i++){
int u, v;
cin >> u >> v; u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 0; i < n; i++){
cin >> c[i];
all[c[i]].push_back(i);
}
slv(0);
int aans = inf;
for(int i = 0; i < n; i++) aans = min(aans, ans[i]);
cout << aans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |