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