#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]; vector <int> a[mn], col[mn]; void pre_dfs(int u, int p){ st[u] = ++ timer_dfs; euler[timer_dfs] = u; for(auto v : a[u]){ if(v == p) continue; pre_dfs(v, u); euler[++ timer_dfs] = u; } ft[u] = timer_dfs; } int higher(int u, int v){ if(d[u] > d[v]) return v; return u; } void build(){ for(int i = 1; i <= timer_dfs; i++) up[i][0] = euler[i]; for(int j = 1; (1 << j) <= timer_dfs; j++){ for(int i = 1; i + (1 << j) - 1 <= timer_dfs; i++){ up[i][j] = higher(up[i][j - 1], up[i + (1 << (j - 1))][j - 1]); } } lg2[0] = -1; for(int i = 1; i <= timer_dfs; i++) lg2[i] = lg2[i >> 1] + 1; } int lca(int u, int v){ if(u == 0) return v; if(v == 0) return u; if(st[u] > st[v]) swap(u, v); int l = st[u], r = st[v], j = lg2[r - l + 1]; int x = higher(up[l][j], up[r - (1 << j) + 1][j]); return x; } int dist(int u, int v){ int p = lca(u, v); return d[u] + d[v] - 2 * d[p]; } 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'; } } 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]; if(n <= 2000){ sub2000::sol(); return; } pre_dfs(1, 0); build(); } 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:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~