#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
int n, k;
namespace sub1{
void solve(){
vector<vector<int>>g(n + 1);
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vector<int>color(n + 1), cnt_color(k, 0);
for(int i = 1; i <= n; i++){
cin >> color[i];
cnt_color[--color[i]]++;
}
int ans = n;
for(int mask = (1 << k) - 1; mask > 0; mask--){
if(__builtin_popcount(mask) < ans){
queue<int>q;
vector<bool>vis(n + 1, false);
for(int i = 1; i <= n; i++){
if(1 << color[i] & mask){
q.push(i);
vis[i] = true;
break;
}
}
while(!q.empty()){
int u = q.front();
q.pop();
for(int& v : g[u]){
if(!vis[v] && (1 << color[v] & mask)){
vis[v] = true;
q.push(v);
}
}
}
int expect = 0;
for(int i = 0; i < k; i++){
if(1 << i & mask){
expect += cnt_color[i];
}
}
if(count(vis.begin(), vis.end(), true) == expect){
ans = __builtin_popcount(mask);
}
}
}
cout << ans - 1;
}
}
namespace sub2{
void solve(){
vector<vector<int>>g(n + 1), vc(k + 1);
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vector<int>color(n + 1);
for(int i = 1; i <= n; i++){
cin >> color[i];
vc[color[i]].emplace_back(i);
}
vector<int>parent(n + 1);
function<void(int)>dfs;
dfs = [&] (int s){
for(int& d : g[s]){
if(d != parent[s]){
parent[d] = s;
dfs(d);
}
}
};
int ans = n;
for(int i = 1; i <= k; i++){
int root = vc[i][0];
dfs(parent[root] = root);
queue<int>q;
for(int& x : vc[i]){
q.push(x);
}
vector<bool>vis_c(k + 1, false), vis(n + 1, false);
vis[root] = true;
vis_c[i] = true;
while(!q.empty()){
int u = q.front();
q.pop();
while(!vis[u = parent[u]]){
if(!vis_c[color[u]]){
for(int& x : vc[color[u]]){
q.push(x);
}
vis_c[color[u]] = true;
}
vis[u] = true;
}
}
minimize(ans, int(count(vis_c.begin(), vis_c.end(), true)));
}
cout << ans - 1;
}
}
namespace sub34{
const int lim = 2e5 + 5;
vector<int>vertex, vc[lim], g[lim];
int ans = lim, color[lim], parent[lim], cnt_child[lim];
bitset<lim>vis, out;
void dfs(int s, bool ins = true){
if(ins){
vertex.emplace_back(s);
}
cnt_child[s] = 1;
for(int& d : g[s]){
if(!vis.test(d) && d != parent[s]){
parent[d] = s;
dfs(d, ins);
cnt_child[s] += cnt_child[d];
}
}
}
void centroid_decomposition(int s){
dfs(parent[s] = s, false);
int centroid = s;
while(true){
bool flag = false;
for(int& d : g[centroid]){
if(d != parent[centroid] && !vis.test(d) && cnt_child[d] > (cnt_child[s] >> 1)){
centroid = d;
flag = true;
break;
}
}
if(!flag){
break;
}
}
vertex.clear();
dfs(parent[centroid] = centroid);
queue<int>q;
bool flag = true;
for(int& x : vc[color[centroid]]){
if(cnt_child[x] == -1){
flag = false;
break;
}
q.push(x);
}
map<int, bool>vis_color, vis_vertex;
vis_color[color[centroid]] = true;
vis_vertex[centroid] = true;
while(!q.empty() && flag){
int u = q.front();
q.pop();
while(!vis_vertex[u = parent[u]]){
if(!vis_color[color[u]]){
for(int& x : vc[color[u]]){
if(cnt_child[x] == -1){
flag = false;
break;
}
q.push(x);
}
if(!flag){
break;
}
vis_color[color[u]] = true;
}
vis_vertex[u] = true;
}
}
if(flag){
minimize(ans, int(vis_color.size()));
}
for(int& x : vertex){
cnt_child[x] = -1;
}
vis.set(centroid);
for(int& d : g[centroid]){
if(!vis.test(d)){
centroid_decomposition(d);
}
}
}
void solve(){
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
for(int i = 1; i <= n; i++){
cin >> color[i];
vc[color[i]].emplace_back(i);
}
centroid_decomposition(1);
cout << ans - 1 << "\n";
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> k;
if(n <= 20){
sub1::solve();
}
else if(n <= 2000){
sub2::solve();
}
else{
sub34::solve();
}
}
