5495: 能源(困难)
[Creator : ]
Description
一天小周周旅行的时候来到了一个神奇的国度,这个国度由 $n$ 个城市组成,这 $n$ 个城市的电网由 $n−1$ 条输电线路组成,而 $1$ 号城市是这个国家的首都。
但是有一天,因为某些原因突然有 $m$ 个城市的电力出现了问题,不巧的是,这时候恰巧是冬天,为了不让民众们忍受寒冷,小周周自告奋勇要修好这些城市的电力。
每一次,小周周可以选择一个城市,然后把这个城市到首都上的所有城市(包括首都和选择的这个城市)的电力修好(如果某个城市的电力本来就是好的那么就没有影响),虽然小周周自告奋勇,但是他还是想知道,最少选择几个城市才能把整个国度的电力都修好。
但是有一天,因为某些原因突然有 $m$ 个城市的电力出现了问题,不巧的是,这时候恰巧是冬天,为了不让民众们忍受寒冷,小周周自告奋勇要修好这些城市的电力。
每一次,小周周可以选择一个城市,然后把这个城市到首都上的所有城市(包括首都和选择的这个城市)的电力修好(如果某个城市的电力本来就是好的那么就没有影响),虽然小周周自告奋勇,但是他还是想知道,最少选择几个城市才能把整个国度的电力都修好。
Input
第一行有两个整数 $n,m\ (1≤m≤n≤10^5)$,表示城市的个数以及出现电力问题的城市数目。
接下来有 $n−1$ 行,每行有两个整数 $u,v$,表示城市 $u$ 和城市 $v$ 之间由一条输电线路相互连接。
接下来一行有 $m$ 个整数,表示 $m$ 个电力出现问题的城市编号。
接下来有 $n−1$ 行,每行有两个整数 $u,v$,表示城市 $u$ 和城市 $v$ 之间由一条输电线路相互连接。
接下来一行有 $m$ 个整数,表示 $m$ 个电力出现问题的城市编号。
Output
输出一个整数,表示小周周最少选择几个城市。
Sample 1 Input
5 4
1 2
1 3
2 4
4 5
2 3 4 5
Sample 1 Output
2