#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() const int mxN = 5e5 + 100; vector<int> adj[mxN], col[mxN]; int sz[mxN], vis[mxN], id[mxN], vis_col[mxN], parent[mxN], cvis[mxN], n, k, ans = mxN; void dfs(int u, int par){ for(auto it : adj[u]){ if(!vis[it] && it ^ par && !vis_col[id[it]]) dfs(it, u); } } void calc_sz(int u, int par){ sz[u] = 1; parent[u] = par; for(auto it : adj[u]){ if(!vis[it] && it ^ par && !vis_col[id[it]]){ calc_sz(it, u); sz[u] += sz[it]; } } } int find_cent(int u, int par, int nby2){ for(auto it : adj[u]){ if(!vis[it] && it ^ par && !vis_col[id[it]] && sz[it] >= nby2){ return find_cent(it, u, nby2); } } return u; } void decompose(int u = 1, int par = -1){ calc_sz(u, -1); int cent = find_cent(u, -1, sz[u] / 2); // dfs(cent, -1); vector<int> q; q.push_back(id[cent]); vector<int> tcol = {id[cent]}; cvis[id[cent]] = 1; int cans = 1; while(q.size()){ auto tp = q.back(); q.pop_back(); if(cans >= mxN) break; if(vis_col[tp]){ cans = mxN; break; } bool flag = 0; for(auto it : col[tp]){ if(parent[it] != -1){ if(vis[parent[it]] || vis_col[id[parent[it]]]){ cans = mxN; break; } if(!cvis[id[parent[it]]]){ q.push_back(id[parent[it]]); cvis[id[parent[it]]] = 1, cans += 1; tcol.push_back(id[parent[it]]); } } } } for(auto it : tcol) cvis[it] = 0; ans = min(ans, cans); vis[cent] = 1, vis_col[id[cent]] = 1; for(auto it : adj[cent]){ if(!vis[it]) decompose(it, u); } } signed main(){ ios::sync_with_stdio(0); cin.tie(nullptr); cin >> n >> k; for(int i = 0, u, v; i < n - 1; ++i){ cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for(int i = 1, x; i <= n; ++i){ cin >> x; id[i] = x; col[x].push_back(i); } decompose(); cout << --ans << "\n"; return 0; }