#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], d[mn], up[mn][20], par[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; par[u] = p; euler[timer_dfs] = u; for(auto v : a[u]){ if(v == p) continue; d[v] = d[u] + 1; 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 { void sol(){ for(int i = 1; i <= n; i++){ col[c[i]].push_back(i); } int min_val = inf; for(int i = 1; i <= k; i++){ int all = 0; for(auto u : col[i]){ if(!all) all = u; else all = lca(all, u); } debug(col[i], all); vector <int> on(k + 1, 0); int Setsuko = 0; for(auto u : col[i]){ int cur = u; while(d[cur] > d[all]){ if(c[cur] != c[all] && !on[c[cur]]){ Setsuko ++; on[c[cur]] = 1; } cur = par[cur]; } } min_val = min(min_val, Setsuko); } 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]; pre_dfs(1, 0); build(); if(n <= 2000) sub2000::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:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~