/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int n, col[N], D = 0, k, s[N], ans, col_cnt[N], id[N], par[N], in_queue[N];
vi g[N], C[N];
bitset<N> vis = 0, used = 0;
void pre(int v, int p){
id[v] = D;
s[v] = 1;
col_cnt[col[v]] = 0;
in_queue[col[v]] = -1;
for(int u: g[v]){
if(u != p && !vis[u]){
pre(u, v);
s[v] += s[u];
}
}
}
void dfs(int v, int p){
col_cnt[col[v]]++;
used[v] = 0;
for(int u: g[v]){
if(u != p && !vis[u]){
par[u] = v;
dfs(u, v);
}
}
}
int num;
int centro(int v, int p){
for(int u: g[v]){
if(u == p || vis[u]) continue;
if(s[u] >= (num+1)/2) return centro(u, v);
}
return v;
}
void f(int v){
++D;
pre(v, v);
num = s[v];
v = centro(v, v);
dfs(v, v);
bool ok = true;
queue<int> q;
q.push(col[v]);
in_queue[col[v]] = 1;
int res = 0;
used[v] = 1;
while(!q.empty() && ok){
++res;
int c = q.front(); q.pop();
for(int u: C[c]){
if(id[u] != D){
ok = false;
break;
}
while(u != v){
used[u] = 1;
if(in_queue[col[u]] == -1){
q.push(col[u]);
in_queue[col[u]] = 1;
}
u = par[u];
}
}
}
if(ok){
ans = min(ans, res);
}
vis[v] = 1;
for(int u: g[v]){
if(!vis[u]) f(u);
}
}
void solve(){
cin >> n >> k;
for(int i = 1; i < n; ++i){
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
for(int i = 1; i <= n; ++i){
int c; cin >> c;
C[c].pb(i);
col[i] = c;
}
ans = k;
f(1);
cout << ans - 1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\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... |