This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
const int MAXN = 2e5;
int n, k, color[MAXN], par[MAXN], s[MAXN], ans = MAXN, curr;
vector<int> g[MAXN], h[MAXN];
bitset<MAXN> r, vis, bad;
void calcSize(int u){
s[u] = 1;
for(int v : g[u]) if(!s[v]) calcSize(v), s[u] += s[v];
}
int find(int u, int p, int sz){
bool f = 1;
while(f){
f = 0;
s[p] -= s[u], s[u] = sz;
for(int v : g[u]){
if(!r[v] && s[v] > sz/2){
p = u, u = v;
f = 1;
break;
}
}
}
return u;
}
void dfs(int u){
vis[color[u]] = 0;
for(int v : g[u]) if(s[v] < s[u] && !r[v]) dfs(v), par[v] = curr * MAXN + u;
}
void decompose(int c){
r[c = curr = find(c, c, s[c])] = 1;
par[c] = curr * MAXN + c;
dfs(c);
int res = 0;
vis[color[c]] = 1;
vector<int> st;
for(int i : h[color[c]]){
if(res == MAXN) break;
if(par[i] / MAXN != c) res = MAXN;
else st.push_back(i);
}
while(!st.empty() && res < MAXN){
int u = st.back(); st.pop_back();
int p = par[u] % MAXN;
if(!vis[color[p]]){
if(bad[color[p]]){
res = MAXN;
break;
}
++res;
for(int v : h[color[p]]){
if(par[v] / MAXN == c && res < MAXN) st.push_back(v);
else res = MAXN;
}
if(res < MAXN) vis[color[p]] = 1;
else bad[color[p]] = 1;
}
}
ans = min(ans, res);
bad[color[c]] = 1;
for(int v : g[c]) if(!r[v]) decompose(v);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int x, y; cin >> n >> k;
for(int i=1; i<n; ++i){
cin >> x >> y; --x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=0; i<n; ++i){
cin >> color[i]; --color[i];
h[color[i]].push_back(i);
}
calcSize(0);
decompose(0);
cout << ans;
}
# | 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... |