#53953. [计蒜之道 2021 公开组预赛 R1] 能源(简单)
[计蒜之道 2021 公开组预赛 R1] 能源(简单)
暂无测试数据。
一天小 x 旅行的时候来到了一个神奇的国度,这个国度由 $n$ 个城市组成,这 $n$ 个城市的电网由 $n-1$ 条输电线路组成,而 $1$ 号城市是这个国家的首都。但是有一天,因为某些原因突然有 $m$ 个城市的电力出现了问题,不巧的是,这时候恰巧是冬天,为了不让民众们忍受寒冷,小 x 自告奋勇要修好这些城市的电力。
每一次,小 x 可以选择一个城市,然后把这个城市到首都上的所有城市(包括首都和选择的这个城市)的电力修好(如果某个城市的电力本来就是好的那么就没有影响),虽然小 x 自告奋勇,但是她还是想知道,她最少选择几个城市才能把整个国度的电力都修好。
输入格式
第一行有两个整数 $n,m$,表示城市的个数以及出现电力问题的城市数目。
接下来有 $n-1$ 行,每行有两个整数 $u , v$,表示城市 $u$ 和城市 $v$ 之间由一条输电线路相互连接。
接下来一行有 $m$ 个整数,表示 $m$ 个电力出现问题的城市编号。
输出格式
输出一个整数,表示小 $x$ 最少选择几个城市。
数据范围
保证 $ 1 \leq m \leq n \leq 16$。
5 4
1 2
1 3
2 4
4 5
2 3 4 5
2