#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pii pair<int, int> #define all(a) a.begin(), a.end() using namespace std; #ifdef LOCAL #include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h" #else #define debug(...) 42 #endif const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9; int n, k, c[mn], up[mn][20], d[mn], st[mn], ft[mn], euler[mn], timer_dfs = 0, lg2[mn], Megumi[mn]; vector <int> a[mn], col[mn]; namespace sub2000 { int on[2005], vis[2005], par[2005], d[2005]; void dfs(int u, int p){ for(auto v : a[u]){ if(v == p) continue; par[v] = u; d[v] = d[u] + 1; dfs(v, u); } } void sol(){ for(int i = 1; i <= n; i++){ col[c[i]].push_back(i); } int min_val = inf; for(int i = 1; i <= n; i++){ queue <int> q; memset(on, 0, sizeof(on)); memset(vis, 0, sizeof(vis)); memset(par, 0, sizeof(par)); on[c[i]] = 1, vis[i] = 1; for(auto u : col[c[i]]) q.push(u); dfs(i, 0); debug(i, col[c[i]]); int res = 0; while(q.size()){ int u = q.front(); q.pop(); while(d[u] > d[i]){ if(vis[u]) break; vis[u] = 1; u = par[u]; debug(u, i); if(!on[c[u]]){ on[c[u]] = 1; res ++; for(auto v : col[c[u]]) q.push(v); } } } debug(min_val, res); min_val = min(min_val, res); } cout << min_val << '\n'; } } namespace full{ int ans = inf, d[mn], vis[mn], par[mn], on[mn], sz[mn], cc[mn]; void pre_dfs(int u, int p){ sz[u] = 1; for(auto v : a[u]){ if(v == p || on[v]) continue; par[v] = u, d[v] = d[u] + 1; pre_dfs(v, u); sz[u] += sz[v]; } } int find(int u, int p, int ovr_sz){ for(auto v : a[u]){ if(v == p || on[v]) continue; if(sz[v] * 2 > ovr_sz) return find(v, u, ovr_sz); } return u; } vector <int> all; void collect(int u, int p){ all.push_back(u); d[u] = d[p] + 1; par[u] = p; for(auto v : a[u]){ if(v == p || on[v]) continue; collect(v, u); } } void decompose(int cen){ pre_dfs(cen, 0); cen = find(cen, 0, sz[cen]); on[cen] = 1, par[cen] = 0, d[cen] = 0; collect(cen, 0); for(auto v : all){ col[c[v]].push_back(v); } queue <int> q; cc[c[cen]] = 1, vis[cen] = 1; for(auto u : col[c[cen]]) q.push(u); // cerr << "Centroid " << cen << '\n'; debug(col[c[cen]]); debug(all); int res = 0; while(q.size()){ int u = q.front(); q.pop(); debug(u, cen); if((int) col[c[u]].size() < Megumi[c[u]]){ res = inf; break; } while(d[u] > d[cen]){ if(vis[u]) break; vis[u] = 1, u = par[u]; if(!cc[c[u]]){ cc[c[u]] = 1; res ++; for(auto v : col[c[u]]) q.push(v); } } } ans = min(ans, res); debug(cen, ans); for(auto v : all){ col[c[v]].clear(); cc[c[v]] = vis[v] = 0; } all.clear(); for(auto v : a[cen]){ if(on[v]) continue; decompose(v); } } void sol(){ decompose(1); cout << ans << '\n'; } } void solve() { cin >> n >> k; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; a[u].push_back(v); a[v].push_back(u); } for(int i = 1; i <= n; i++){ cin >> c[i]; Megumi[c[i]] ++; } full::sol(); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define task "Kawabata" if (fopen(task".INP", "r")) { freopen(task".INP", "r", stdin); freopen(task".OUT", "w", stdout); } int t = 1; // cin >> t; while (t--) solve(); return 0; } // Don't wanna lose anymore T_T // Never let me go - Kazuo Ishiguro

capital_city.cpp: In function 'int main()':
capital_city.cpp:179:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:180:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~