← 返回题目列表

Codeforces · 1881/F

F. 最小最大距离

中文机器翻译题面 查看原题

您有一棵具有 $$$n$$$ 个顶点的树,其中一些已被标记。树是无环的连通无向图。

让 $$$f_i$$$ 表示从顶点 $$$i$$$ 到任何标记顶点的最大距离。

你的任务是找到所有顶点中 $$$f_i$$$ 的最小值。

例如,在示例所示的树中,标记了顶点 $$$2$$$、$$$6$$$ 和 $$$7$$$。那么数组 $$$f(i) = [2, 3, 2, 4, 4, 3, 3]$$$。最小值 $$$f_i$$$ 用于顶点 $$$1$$$ 和 $$$3$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) - 分别是树中的顶点数和标记顶点数。

每个测试用例的第二行包含 $$$k$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le n, a_{i-1} < a_i$$$) - 标记顶点的索引。

接下来的 $$$n - 1$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ — 由第 $$$i$$$ 条边连接的顶点的索引。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所有顶点中 $$$f_i$$$ 的最小值。

示例

输入 #1

6
7 3
2 6 7
1 2
1 3
2 4
2 5
3 6
3 7
4 4
1 2 3 4
1 2
2 3
3 4
5 1
1
1 2
1 3
1 4
1 5
5 2
4 5
1 2
2 3
1 4
4 5
10 8
1 2 3 4 5 8 9 10
2 10
10 5
5 3
3 1
1 7
7 4
4 9
8 9
6 1
10 9
1 2 4 5 6 7 8 9 10
1 3
3 9
9 4
4 10
10 6
6 7
7 2
2 5
5 8

输出 #1

2
2
0
1
4
5

输入 #2

3
6 1
3
1 2
1 3
3 4
3 5
2 6
5 3
1 2 5
1 2
1 3
2 4
3 5
7 1
2
3 2
2 6
6 1
5 6
7 6
4 5

输出 #2

0
2
0