#include<bits/stdc++.h>
using namespace std;
const int NMAX = 500000+1;
const int INFINI = 1e9;
int boss[NMAX];
int N, K;
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]);
}
bool vuCompo[NMAX];
vector<int> parcoursVu;
int numero[NMAX];
int dansFamille[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)
{
if(prem[dansFamille[noeud]] == 0)
{
prem[dansFamille[noeud]] = noeud;
}
boss[noeud] = prem[dansFamille[noeud]];
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];
void merge(int a, int b)
{
a = findBoss(a);
b = findBoss(b);
if(a == b) return;
if(numero[b] < numero[a])
{
swap(a, b);
}
boss[b] = a;
nbComposantesTotal--;
}
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];
bool assure[NMAX];
set<int> cheminsEntreCompo[NMAX];
void faireCompo()
{
for(int iVal = 1; iVal <= N; iVal++)
{
int bossNoeud = findBoss(iVal);
for(auto pro : chemins[iVal])
{
int bossPro = findBoss(pro);
if(bossPro != bossNoeud) cheminsEntreCompo[bossNoeud].insert(bossPro);
}
}
}
void parcoursFin(int noeud, int anc)
{
// cout << noeud << " mkm " << endl;
for(int pro : cheminsEntreCompo[noeud])
{
// cout << noeud << " " << pro << endl;
if(pro == anc) continue;
// cout << noeud << " " << pro << endl;
//*
if(!assure[noeud]) nbComposantesTotal --;
assure[noeud] = true;
/** */
parcoursFin(pro, noeud);
}
}
//faire un graphique parrapport à composantes
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
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;
clubs[famille].push_back(i);
dansFamille[i] = famille;
}
parcourir(1, 0);
base(1, 0, parcoursLCA.size());
// for(int i : parcoursLCA) cout << parcoursVersNoeud[i] << " ";
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];
// cout << noeudLCA << endl;
for(int iElem : clubs[iFamille])
{
while(numero[iElem] > numero[noeudLCA])
{
merge(iElem, prem[iFamille]);
if((numero[pere[iElem]] > numero[findBoss(iElem)]) && (findBoss(pere[iElem]) == findBoss(iElem)))
iElem = findBoss(iElem);
else
iElem = pere[iElem];
}
}
merge(noeudLCA, prem[iFamille]);
}
/*
for(int i = 1; i <= N; i++)
{
cout << findBoss(i) << " ";
}
cout << endl;
/** */
if(nbComposantesTotal == 1)
{
cout << 0;
return 0;
}
/*
for(int i = 1; i <= N; i++)
{
cout << findBoss(i) << " ";
}
cout << endl;
cout << nbComposantesTotal << endl;
/** */
faireCompo();
int origine = 1;
while((origine <= N) && (cheminsEntreCompo[findBoss(origine)].size() == 1)) origine++;
parcoursFin(findBoss(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);
}
