// #pragma GCC optimize("Ofast")
// #pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
#define mkp make_pair
#define txt freopen("shortcut.in", "r", stdin), freopen("shortcut.out", "w", stdout);
const int N = 2e5 + 100, K = 50, inf = 1e14, mod = 1e9 + 7;
const double eps = 1e-6;
vector<int> gr[N];
int Col[N];
vector<int> C[N];
bool blocked[N];
int CntCol[N];
bool vis[N];
bool usCol[N];
int cnt[N];
bool used[N];
int P[N];
void dfs(int x, int par)
{
P[x] = par;
cnt[x] = 1;
for(auto i : gr[x])
{
if(i == par || used[i])
continue;
dfs(i, x);
cnt[x] += cnt[i];
}
}
int find(int x, int par, int m)
{
bool res = (cnt[x] >= ((m + 1) / 2));
for(auto i : gr[x])
{
if(i == par || used[i])
continue;
res = min(res, (cnt[i] <= ((m + 1) / 2)));
int k = find(i, x, m);
if(k != -1)
return k;
}
if(res)
return x;
return -1;
}
vector<int> vec;
void kol(int x, int par)
{
vec.push_back(x);
for(auto i : gr[x])
{
if(i == par || used[i])
continue;
kol(i, x);
}
}
int solve(int x)
{
if(vec.size() == 1)
return 1e9;
// return (C[Col[x]].size() == 1 ? 0 : 1e9);
int cent = find(x, 0, vec.size());
dfs(cent, 0);
used[cent] = 1;
for(auto i : vec)
CntCol[Col[i]]++;
for(auto i : vec)
{
if(CntCol[Col[i]] != C[Col[i]].size())
blocked[Col[i]] = 1;
}
bool fl = 0;
int res = 0;
vis[0] = 1;
if(!blocked[Col[x]])
{
fl = 1;
queue<int> Q;
for(auto i : C[Col[x]])
Q.push(i);
usCol[Col[x]] = 1;
while(!Q.empty())
{
int y = Q.front();
Q.pop();
while(!vis[y])
{
vis[y] = 1;
if(blocked[Col[y]])
{
fl = 0;
break;
}
if(!usCol[Col[y]])
{
usCol[Col[y]] = 1;
res++;
for(auto i : C[Col[y]])
Q.push(i);
}
y = P[y];
}
if(!fl)
break;
}
}
if(!fl)
res = 1e9;
for(auto i : vec)
usCol[Col[i]] = vis[i] = CntCol[i] = 0;
for(auto i : gr[cent])
{
if(used[i])
continue;
vec.clear();
kol(i, cent);
res = min(res, solve(i));
}
return res;
}
void solve()
{
int n, k;
cin >> n >> k;
for(int i = n - 1, a, b; i--;)
{
cin >> a >> b;
gr[a].push_back(b);
gr[b].push_back(a);
}
for(int i = 1; i <= n; i++)
{
cin >> Col[i];
C[Col[i]].push_back(i);
vec.push_back(i);
}
dfs(1, 0);
int ans = solve(1);
assert(ans < n);
cout << ans << '\n';
}
signed main()
{
// txt;
// ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T = 1;
for(; T--; solve());
}
/*
*/
# | 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... |