이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin >> n >> k;
vector<vector<int>> adj(n+1);
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
vector<int> col(n+1);
for(int i=1;i<=n;i++)cin>>col[i];
vector<int> nodes(k+1);
function<void(int,int,int)> dfs = [&](int x,int par,int dep){
nodes[col[x]] = x;
for(int&i:adj[x])if(i!=par)dfs(i,x,dep+1);
};
dfs(1,0,1);
vector<vector<int>> compoadj(k+1);
for(int i=1;i<=k;i++){
set<int> bad;
function<bool(int,int)> pdfs = [&](int x,int p){
bool found = col[x]==i;
for(int&i:adj[x])if(i!=p)if(pdfs(i,x))found=true;
if(found)bad.insert(col[x]);
return found;
};
pdfs(nodes[i],0);
for(int x:bad)compoadj[i].emplace_back(x);
}
vector<bool> visited(k+1);
int siz = 0;
function<void(int)> compodfs = [&](int x){
if(visited[x])return;
siz++;
visited[x]=true;
for(int&i:compoadj[x])compodfs(i);
};
int ans = n;
for(int i=1;i<=k;i++){
siz = 0;
visited = vector<bool>(k+1);
compodfs(i);
ans = min(ans,siz-1);
}
cout << ans << '\n';
}
# | 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... |