#include <algorithm> #include <iostream> #include <queue> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<vector<int>> adj(n + 1); for (int i = 0, u, v; i < n - 1; ++i) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } vector<int> c(n + 1), count_in(k + 1); for (int i = 1; i <= n; ++i) { cin >> c[i]; count_in[c[i]]++; } vector<bool> is_alr_centroid(n + 1); vector<int> subtree_size(n + 1); auto find_subtree_size = [&](auto &&self, int u, int p) -> int { subtree_size[u] = 1; for (int &i : adj[u]) { if (i == p || is_alr_centroid[i]) { continue; } subtree_size[u] += self(self, i, u); } return subtree_size[u]; }; auto find_centroid = [&](auto &&self, int n, int u, int p) -> int { pair<int, int> best = {0, 0}; for (int &i : adj[u]) { if (i == p || is_alr_centroid[i]) { continue; } best = max(best, {subtree_size[i], i}); } if (best.first <= n / 2) { return u; } return self(self, n, best.second, u); }; int ans = n; vector<bool> used_color(k + 1), vis(n + 1); vector<int> par(n + 1), cur_in(k + 1); vector<vector<int>> towns(k + 1); auto check_node = [&](int n, int u) { par[u] = u; vector<int> colors_seen, nodes_seen; auto dfs = [&](auto &&self, int u, int p) -> void { colors_seen.push_back(c[u]); nodes_seen.push_back(u); towns[c[u]].push_back(u); for (int &i : adj[u]) { if (i == p || is_alr_centroid[i]) { continue; } par[i] = u; self(self, i, u); } }; dfs(dfs, u, 0); vector<int> colors; queue<int> q; colors.push_back(c[u]); used_color[c[u]] = true; for (int &i : towns[c[u]]) { q.push(i); } while (!q.empty()) { int i = q.front(); q.pop(); if (vis[i] || is_alr_centroid[i]) { continue; } cur_in[c[i]]++; vis[i] = true; if (!used_color[c[i]]) { colors.push_back(c[i]); used_color[c[i]] = true; for (int &city : towns[c[i]]) { q.push(city); } } if (!vis[par[i]] && !is_alr_centroid[par[i]]) { q.push(par[i]); } } bool good = true; for (int &c : colors) { good &= cur_in[c] == count_in[c]; cur_in[c] = 0; used_color[c] = false; } for (int &c : colors_seen) { towns[c].clear(); } for (int &u : nodes_seen) { vis[u] = false; } if (good) { ans = min(ans, int(colors.size())); } }; auto centroid_decomp = [&](auto &&self, int u) -> void { find_subtree_size(find_subtree_size, u, 0); int centroid = find_centroid(find_centroid, subtree_size[u], u, 0); check_node(subtree_size[u], centroid); is_alr_centroid[centroid] = true; for (int &i : adj[centroid]) { if (is_alr_centroid[i]) { continue; } self(self, i); } }; centroid_decomp(centroid_decomp, 1); cout << ans - 1 << '\n'; }