#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int maxN = 500'000;
vector<int> edge[1+maxN];
vector<int> parent(1+maxN, 0);
vector<int> subtree(1+maxN, 1);
vector<int> max_child(1+maxN, -1);
void dfs1(int u)
{
for(int v: edge[u])
{
if(parent[u] == v) continue;
parent[v] = u;
dfs1(v);
subtree[u] += subtree[v];
if(max_child[u] == -1 || subtree[v] > subtree[ max_child[u] ])
max_child[u] = v;
}
}
struct state
{
int i;
int c;
};
bool operator < (state A, state B)
{
return A.i < B.i;
}
int S[1+maxN];
vector<int> state_count(1+maxN, 0);
set<state>* T[1+maxN];
void add_state(int u, state x)
{
// cerr << "add_state " << u << ' ' << x.i << ' ' << x.c << '\n';
set<state>::iterator it = T[u]->find(x);
if(it == T[u]->end())
{
// cerr << "case A\n";
if(x.c != state_count[x.i])
T[u]->insert(x);
}
else
{
// cerr << "case B\n";
int ct = it->c + x.c;
T[u]->erase(it);
if(ct != state_count[x.i])
{
T[u]->insert(state{x.i, ct});
}
}
}
int bad_edge_count = 0;
bool dfs2(int u) //returns if we have found any bad edges yet.
{
// cerr << "dfs2 " << u << ' ' << max_child[u] << '\n';
bool flag = 0;
if(max_child[u] == -1)
{
// cerr << "case 1\n";
T[u] = new set<state>;
add_state(u, state{S[u], 1});
}
else
{
for(int v: edge[u])
{
if(v == parent[u]) continue;
// cerr << u << " -> " << v << '\n';
flag |= dfs2(v);
}
// cerr << "case 2\n";
T[u] = T[ max_child[u] ];
// cerr << "x\n";
add_state(u, state{S[u], 1});
// cerr << "check X\n";
for(int v: edge[u])
{
// cerr << "v = " << v << '\n';
if(v == parent[u] || v == max_child[u]) continue;
for(state s: *(T[v]))
add_state(u, s);
T[v]->clear();
}
}
if(T[u]->size() == 0 && u != 1)
{
if(!flag)
{
// cerr << "adding bad edge at " << u << '\n';
bad_edge_count++;
}
return 1;
}
else
{
return flag;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
for(int i = 1; i <= N-1; i++)
{
int A, B;
cin >> A >> B;
edge[A].push_back(B);
edge[B].push_back(A);
}
for(int i = 1; i <= N; i++)
{
cin >> S[i];
state_count[ S[i] ]++;
}
// cerr << "check 0\n";
parent[1] = 1;
dfs1(1);
// cerr << "check 1\n";
dfs2(1);
// cerr << "check 2\n";
int res = (bad_edge_count / 2) + (bad_edge_count % 2);
cout << res << '\n';
}
