#include <bits/stdc++.h>
using namespace std;
#define int long long
void strat1(int n){
int k;
cin >> k;
vector<vector<int>> adj(n+1);
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
vector<int> col(n+1);
for(int i=1;i<=n;i++)cin>>col[i];
vector<int> nodes(k+1);
function<void(int,int,int)> dfs = [&](int x,int par,int dep){
nodes[col[x]] = x;
for(int&i:adj[x])if(i!=par)dfs(i,x,dep+1);
};
dfs(1,0,1);
vector<vector<int>> compoadj(k+1);
for(int i=1;i<=k;i++){
set<int> bad;
function<bool(int,int)> pdfs = [&](int x,int p){
bool found = col[x]==i;
for(int&i:adj[x])if(i!=p)if(pdfs(i,x))found=true;
if(found)bad.insert(col[x]);
return found;
};
pdfs(nodes[i],0);
for(int x:bad)compoadj[i].emplace_back(x);
}
vector<bool> visited(k+1);
int siz = 0;
function<void(int)> compodfs = [&](int x){
if(visited[x])return;
siz++;
visited[x]=true;
for(int&i:compoadj[x])compodfs(i);
};
int ans = n;
for(int i=1;i<=k;i++){
siz = 0;
visited = vector<bool>(k+1);
compodfs(i);
ans = min(ans,siz-1);
}
cout << ans << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
if(n<=2000){
strat1(n);
return 0;
}
int k;
cin >> k;
vector<vector<int>> adj(n+1);
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
vector<int> colcor(n+1);
vector<int> col(n+1);
for(int i=1;i<=n;i++)cin>>colcor[i];
function<void(int,int,int)> dfs = [&](int x,int par,int idx){
col[idx] = colcor[x];
for(int&i:adj[x])if(i!=par)dfs(i,x,idx+1);
};
for(int i=1;i<=n;i++)if(adj[i].size()==1){
dfs(i,0,1);
break;
}
vector<int> minidx(k+1);
vector<int> maxidx(k+1);
for(int i=1;i<=n;i++)maxidx[col[i]]=i;
for(int i=n;i;i--)minidx[col[i]]=i;
vector<vector<int>> compoadj(k+1);
vector<vector<int>> comporevadj(k+1);
for(int i=1;i<=k;i++){
for(int x=minidx[i];x<=maxidx[i];x++){
if(col[x]!=i){
compoadj[i].emplace_back(col[x]);
comporevadj[col[x]].emplace_back(i);
x = maxidx[col[x]];
}
}
}
vector<bool> visited(k+1);
vector<int> order;
vector<int> siz(k+1);
vector<int> mycompo(k+1);
function<void(int)> topo = [&](int x){
if(visited[x])return;
visited[x]=true;
for(int&i:compoadj[x])topo(i);
order.emplace_back(x);
};
for(int i=1;i<=k;i++)if(!visited[i])topo(i);
reverse(order.begin(),order.end());
function<void(int,int)> cr_dfs = [&](int x,int compo){
if(mycompo[x]){
if(mycompo[x]!=compo)siz[mycompo[x]]=n+1;
return;
}
siz[compo]++;
mycompo[x] = compo;
for(int&i:comporevadj[x])cr_dfs(i,compo);
};
int components = 0;
int ans = n+1;
for(int i=0;i<k;i++)if(mycompo[order[i]]==0)cr_dfs(order[i],++components);
for(int i=1;i<=components;i++){
ans = min(ans,siz[components]-1);
}
cout << ans << '\n';
}
