#53955. [计蒜之道 2021 公开组预赛 R1] 能源(困难)

    ID: 53955 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>计蒜客赛事普及T2图论基础深度优先搜索图和深度优先搜索题单魔扣OJ

[计蒜之道 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 10^5$。

5 4
1 2
1 3
2 4
4 5
2 3 4 5
2