合并
题号：NC53302
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2019 Day4 T2「合併 / Mergers」
JOI合众国有N个城市，编号为，并且有N-1条高速公路，编号为。第条高速公路双向连接城市A_i与B_i。一个人可以利用高速公路从任意一个城市到达另一个城市。
目前，JOI合众国有K个州，编号为，城市属于州S_j。任意一个州内至少有一个城市。
JOI合众国总统K先生害怕国家会分裂。JOI合众国被称作可分裂的当且仅当所有城市可以被划分为X组和Y组，并且满足以下条件：
  • 所有城市属于X组或Y组之一；
  • X组中至少有一个城市；Y组中至少有一个城市；
  • 对于任意一个州，所有所属州相同的城市都在同一组；
  • 一个人可以从X组的任意一个城市出发，通过高速公路到达X组的任意一个城市；
  • 一个人可以从Y组的任意一个城市出发，通过高速公路到达Y组的任意一个城市。
K先生将要合并一些州，使得JOI合众国是不可分裂的。当他合并州的时候，他会选择两个州，然后把这两个州合并成一个新州。新州下辖的城市为原来两个州所有下辖的城市。K先生想要在合并次数最少的情况下完成合并任务，使得JOI合众国是不可分裂的。
注意，如果JOI合众国只有一个州，那么它是不可分裂的。
写一个程序，在给定所有城市，州和高速公路的信息的情况下，计算使得JOI合众国不可分裂的最小合并次数。

输入描述:

从标准输入读入以下数据：
第一行两个正整数N,K，表示JOI合众国有N个城市K个州；
接下来N-1行，每行两个整数A_i,B_i，描述JOI合众国内部高速公路的情况。
接下来N行，每行一个正整数S_j，表示j号城市属于S_j州。

输出描述:

输出一个整数到标准输出，表示使得JOI合众国不可分裂的最小合并次数。
示例1

输入

复制 
5 4
1 2
2 3
3 4
3 5
1
2
1
3
4

输出

复制 
1

说明

在这组样例中，初始情况的JOI合众国是可分裂的，例如，如果将1,2,3,4号城市分到X组，5号城市分到Y组，这样是满足可分裂的条件的。
如果K先生将3,4号州合并为一个州，JOI合众国就不可分裂了，因此答案为1。
示例2

输入

复制 
5 4
1 2
2 3
3 4
4 5
1
2
3
4
1

输出

复制 
0

说明

在这组样例中，初始情况JOI合众国就不可分裂，因此答案是0。
示例3

输入

复制 
2 2
1 2
1
2

输出

复制 
1

备注:

对于全部数据，，保证利用高速公路可以从任意一个城市到达另一个城市，对于任意，都存在使得。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3040