需要注意的是，这个题当把一个颜色合并进选择的颜色后，会导致一些其他的颜色原本无法影响最开始选择的颜色，但是合并后会影响了。也就是说影响关系是具有传递性的。

因此考虑如果设定一个颜色 $i$ 为首都需要将另一个颜色 $j$ 合并进 $i$ ，那么加边 $j \to i$ 。这样加边后，显然只需要一次缩点就能求出答案。具体来说，最后选择的一定是入度为 $0$ 的点，并且需要合并的次数就是这个点的大小 $-1$ 。

考虑怎么进行加边。我们考虑以 $i$ 作为首都，那么显然将 $i$ 颜色建立虚树后所有虚数边上的点的颜色都需要合并进 $i$ 。但是直接这么做边数是 $O(n^2)$ 的。由于这个东西加重边不会有问题，我们可以转化为对于颜色 $i$ 的所有点按照 $\text{dfs}$ 序排序后路径对颜色连边，倍增优化建图即可。

复杂度 $O(n \log n)$ ，有点卡常。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 4000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , k;
int A[200006];

vi G[200006] , g[MAXN];
int cne;

void ade( int u , int v ) {
//	printf("%d %d\n",u,v);
//	++ cne;
	g[u].pb( v );
}

int J[200006][18] , nd[200006][18] , cn , dep[200006];
int dfn[MAXN] , cnt;
void dfs( int u , int f ) {
	dfn[u] = ++ cnt;
	for( int v : G[u] ) if( v != f ) {
		dep[v] = dep[u] + 1;
		J[v][0] = u , nd[v][0] = v;
		for( int k = 1 ; k <= 17 ; ++ k ) if( J[J[v][k - 1]][k - 1] )
			nd[v][k] = ++ cn , ade( nd[v][k - 1] , nd[v][k] ) , ade( nd[J[v][k - 1]][k - 1] , nd[v][k] ),
			J[v][k] = J[J[v][k - 1]][k - 1];
		dfs( v , u );
	}
}

vi pr[MAXN];
void addit( int c , int u , int v ) {
	if( dep[u] < dep[v] ) swap( u , v );
	if( dep[u] != dep[v] ) for( int k = 17 ; k >= 0 ; -- k ) if( dep[J[u][k]] >= dep[v] ) ade( nd[u][k] , c ) , u = J[u][k];
	if( u == v ) {
		ade( v , c );
		return;
	}
	per( k , 17 , 0 ) if( J[u][k] != J[v][k] )
		ade( nd[u][k] , c ) , ade( nd[v][k] , c ) , u = J[u][k] , v = J[v][k];
	ade( u , c ) , ade( v , c ) , ade( J[u][0] , c );
}

int sz[MAXN] , dft[MAXN] , low[MAXN] , clo , bel[MAXN] , stk[MAXN] , top , ins[MAXN] , scc;
void tarjan( int u ) {
	dft[u] = low[u] = ++ clo;
	stk[++ top] = u , ins[u] = 1;
	for( int v : g[u] ) {
		if( !dft[v] ) tarjan( v ) , low[u] = min( low[u] , low[v] );
		else if( ins[v] ) low[u] = min( low[u] , dft[v] );
	}
	if( dft[u] == low[u] ) {
		int x;
		++ scc;
		do {
			x = stk[top--];
			ins[x] = 0;
			bel[x] = scc;
		} while( x != u );
	}
}

int ind[MAXN];
void solve() {
	cin >> n >> k;
	rep( i , 2 , n ) {
		int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v ) , G[v].pb( u );
	}
	cn = n + k;
	rep( i , 1 , n ) scanf("%d",A + i) , ade( A[i] + n , i ) , pr[A[i]].pb( i );
	dep[1] = nd[1][0] = 1 , dfs( 1 , 1 );
	rep( i , 1 , k ) {
		sort( all( pr[i] ) , [&]( int a , int b ) { return dfn[a] < dfn[b]; } );
		rep( j , 0 , pr[i].size() - 1 ) {
			int u = pr[i][j] , v = pr[i][( j + 1 ) % pr[i].size()];
			addit( i + n , u , v );
		}
	}
	rep( i , 1 , cn ) if( !dft[i] ) tarjan( i );
	rep( i , 1 , cn ) 
		for( int v : g[i] ) if( bel[v] != bel[i] ) ++ ind[bel[v]];
	rep( i , n + 1 , n + k ) ++ sz[bel[i]];
//	rep( i , 1 , cn )
//		printf("%d ",bel[i]); puts("");
	int as = 0x3f3f3f3f;
	rep( i , 1 , scc ) if( !ind[i] ) 
		as = min( as , sz[i] - 1 );
//	cout << cn << endl;
	cout << as << endl;
}

signed main() {
//	freopen("03-03.in" , "r" , stdin);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}