#include<bits/stdc++.h>
using namespace std;
const int NMAX = 500000+1;
const int INFINI = 1e9;
int boss[NMAX];
vector<int> chemins[NMAX];
int prem[NMAX];
int nbComposantesTotal;
int findBoss(int noeud)
{
if(boss[noeud] == noeud) return noeud;
return boss[noeud] = findBoss(boss[noeud]);
}
int sizeComp[NMAX];
void merge(int a, int b)
{
a = findBoss(a);
b = findBoss(b);
if(a == b) return;
if(sizeComp[b]>sizeComp[a])
{
swap(a, b);
}
sizeComp[a] += sizeComp[b];
boss[b] = a;
nbComposantesTotal--;
}
bool vuCompo[NMAX];
vector<int> parcoursVu;
int numero[NMAX];
int nbSuiteMaint;
/*
void parcourir(int noeud, int anc)
{
nbSuiteMaint++;
numero[noeud] = nbSuiteMaint;
int bossNoeud = findBoss(noeud);
if(vuCompo[bossNoeud])
{
while((findBoss(*parcoursVu.rbegin()) != findBoss(bossNoeud))&&(!parcoursVu.empty()))
{
merge(bossNoeud, *parcoursVu.rbegin());
parcoursVu.pop_back();
}
}
else
vuCompo[bossNoeud] = true;
parcoursVu.push_back(noeud);
for(int pro : chemins[noeud])
{
if(pro == anc) continue;
int res = 0;
parcourir(pro, noeud); //Avoir
parcoursVu.push_back(noeud);
}
//AAdapter
}
/** */
vector<int> parcoursLCA;
int placeDansParc[NMAX];
int parcoursVersNoeud[NMAX];
int pere[NMAX];
void parcourir(int noeud, int anc)
{
pere[noeud] = anc;
nbSuiteMaint++;
numero[noeud] = nbSuiteMaint;
parcoursVersNoeud[nbSuiteMaint] = noeud;
placeDansParc[noeud] = parcoursLCA.size();
parcoursLCA.push_back(numero[noeud]);
for(int pro : chemins[noeud])
{
if(pro == anc) continue;
parcourir(pro, noeud);
parcoursLCA.push_back(numero[noeud]);
}
}
int arbre[NMAX*2+1];
pair<int, int> debFin[NMAX*2+1];
int base(int noeud, int deb, int fin)
{
debFin[noeud] = {deb, fin};
if(deb == fin-1) return arbre[noeud] = parcoursLCA[deb];
int milieu = (deb+fin)/2;
return arbre[noeud] = min(base(noeud*2, deb, milieu), base(noeud*2+1, milieu, fin));
}
int trouverMin(int noeud, int deb, int fin)
{
if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return INFINI;
if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin)) return arbre[noeud];
return min(trouverMin(noeud*2, deb, fin), trouverMin(noeud*2+1, deb, fin));
}
vector<int> clubs[NMAX];
int dejaVU[NMAX];
bool assure[NMAX];
void parcoursFin(int noeud, int anc)
{
// cout << noeud << " mkm " << endl;
for(int pro : chemins[noeud])
{
// cout << noeud << " " << pro << endl;
if(pro == anc) continue;
// cout << noeud << " " << pro << endl;
//*
if(findBoss(pro) != findBoss(noeud))
{
if(!assure[findBoss(noeud)]) nbComposantesTotal --;
assure[findBoss(noeud)] = true;
}
/** */
parcoursFin(pro, noeud);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
nbComposantesTotal = K;
nbSuiteMaint = 0;
for(int i = 1; i <= N-1; i++)
{
int a, b;
cin >> a>>b;
chemins[a].push_back(b);
chemins[b].push_back(a);
}
for(int i = 1; i <= N; i++)
{
int famille;
cin >> famille;
if(prem[famille] == 0)
{
prem[famille] = i;
}
clubs[famille].push_back(i);
boss[i] = prem[famille];
sizeComp[i] = 1;
}
parcourir(1, 0);
base(1, 0, parcoursLCA.size());
// for(int i : parcoursLCA) cout << parcoursVersNoeud[i] << " ";
// cout << endl;
for(int iFamille = 1; iFamille <= K; iFamille++)
{
// cout << "deb " << iFamille << endl;
int minElem = INFINI, maxElem = 0;
for(int iElem : clubs[iFamille])
{
int posElem = placeDansParc[iElem];
minElem = min(minElem, posElem);
maxElem = max(maxElem, posElem);
}
int lca = trouverMin(1, minElem, maxElem+1);
int noeudLCA = parcoursVersNoeud[lca];
for(int iElem : clubs[iFamille])
{
while(iElem != noeudLCA)
{
if(dejaVU[iElem] == iFamille) break;
dejaVU[iElem] = iFamille;
merge(iElem, prem[iFamille]);
iElem = pere[iElem];
}
}
merge(noeudLCA, prem[iFamille]);
}
if(nbComposantesTotal == 1)
{
cout << 0;
return 0;
}
/*
for(int i = 1; i <= N; i++)
{
cout << findBoss(i) << " ";
}
cout << endl;
cout << nbComposantesTotal << endl;
/** */
int origine = 1;
while((origine <= N) && (chemins[origine].size() == 1)) origine++;
parcoursFin(origine, 0);
// cout << nbComposantesTotal<< "\n";
double rep = nbComposantesTotal;
double autre = 2;
// for(int i = 1; i <= N; i++) cout << assure[i] << " ";
//cout << endl;
cout << ceil(rep/autre);
}
