CF1881F.Minimum Maximum Distance

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You have a tree with $n$ vertices, some of which are marked. A tree is a connected undirected graph without cycles.

Let $f_i$ denote the maximum distance from vertex $i$ to any of the marked vertices.

Your task is to find the minimum value of $f_i$ among all vertices.

For example, in the tree shown in the example, vertices $2$ , $6$ , and $7$ are marked. Then the array $f(i) = [2, 3, 2, 4, 4, 3, 3]$ . The minimum $f_i$ is for vertices $1$ and $3$ .

输入格式

The first line contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ( $1 \le k \le n \le 2 \cdot 10^5$ ) — the number of vertices in the tree and the number of marked vertices, respectively.

The second line of each test case contains $k$ integers $a_i$ ( $1 \le a_i \le n, a_{i-1} < a_i$ ) — the indices of the marked vertices.

The next $n - 1$ lines contain two integers $u_i$ and $v_i$ — the indices of vertices connected by the $i$ -th edge.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

输出格式

For each test case, output a single integer — the minimum value of $f_i$ among all vertices.

输入输出样例

输入#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
2
0

首页