#P17870. [Ontak2019]WIR

[Ontak2019]WIR

— 病毒传播

有 nn 座城市,由 n−1n-1 条道路连接成一棵树。最初有 kk 座城市感染病毒。

病毒可以沿道路从一个已感染城市传播到相邻城市,传播一次需要一小时。每个城市在同一时刻最多向一个相邻城市传播病毒;不同城市可以同时传播。一个城市感染完成后,从下一小时起即可向其他城市传播,原来已经感染的城市仍保持感染。

求让全部城市感染所需的最少小时数。传播顺序可以自由安排。

输入格式

第一行两个整数 n,kn,k。

第二行 kk 个两两不同的整数,表示初始感染的城市编号。

接下来 n−1n-1 行,每行两个整数 ai,bia_i,b_i,表示一条道路。

输出格式

输出一个整数,表示感染全部城市所需的最少小时数。

数据范围

1≤n≤1051\le n\le10^5,1≤k≤min⁡(n,16)1\le k\le\min(n,16)。城市编号在 [1,n][1,n] 内,保证道路构成树。

子任务 附加限制 分值
1 n≤16n\le16 5
2 n≤300,k≤3n\le300,k\le3 20
3 n≤1000,k=2n\le1000,k=2
4 n≤1000,k=3n\le1000,k=3 10
5 k=1k=1 5
6 k=2k=2 30
7 k=3k=3 10

原题总约束允许 k≤16k\le16,子任务表只列到 k≤3k\le3;标程支持总约束中的16个源点。

样例 1

输入:

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

输出:

2

样例 2

输入:

4 1
1
1 2
1 3
2 4

输出:

2