Blocking Chips

题意翻译

一棵大小为 $n$ 的树，有 $k$ 个人，第 $i$ 个人在结点 $a_i$。 从第 $1$ 秒开始，依次操作第 $1,2,3,...,k,1,2,3,...,k,1,2,3,...,k,...$ 个人，每秒操作一个人，把这个人移动到没有被走过的结点（包括其他人走过的）。当不能移动时结束。 问最多能操作多少次，多测。

题目描述

You are given a tree, consisting of $ n $ vertices. There are $ k $ chips, placed in vertices $ a_1, a_2, \dots, a_k $ . All $ a_i $ are distinct. Vertices $ a_1, a_2, \dots, a_k $ are colored black initially. The remaining vertices are white. You are going to play a game where you perform some moves (possibly, zero). On the $ i $ -th move ( $ 1 $ -indexed) you are going to move the $ ((i - 1) \bmod k + 1) $ -st chip from its current vertex to an adjacent white vertex and color that vertex black. So, if $ k=3 $ , you move chip $ 1 $ on move $ 1 $ , chip $ 2 $ on move $ 2 $ , chip $ 3 $ on move $ 3 $ , chip $ 1 $ on move $ 4 $ , chip $ 2 $ on move $ 5 $ and so on. If there is no adjacent white vertex, then the game ends. What's the maximum number of moves you can perform?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of vertices of the tree. Each of the next $ n - 1 $ lines contains two integers $ v $ and $ u $ ( $ 1 \le v, u \le n $ ) — the descriptions of the edges. The given edges form a tree. The next line contains a single integer $ k $ ( $ 1 \le k \le n $ ) — the number of chips. The next line contains $ k $ integers $ a_1, a_2, \dots, a_k $ ( $ 1 \le a_i \le n $ ) — the vertices with the chips. All $ a_i $ are distinct. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each testcase, print a single integer — the maximum number of moves you can perform.

输入输出样例

输入样例 #1

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

输出样例 #1

2
0
1
2
0

题目大意：
一个包含n个顶点的树，有k个筹码，分别放在顶点a1, a2, ..., ak上。所有ai最初都是黑色的，其余顶点是白色的。你将进行一系列操作（可能为零），在第i次操作（1为起始）时，你将第((i - 1) mod k + 1)个筹码从当前位置移动到一个相邻的白色顶点，并将该顶点染成黑色。如果k=3，则在第1次操作移动筹码1，在第2次操作移动筹码2，在第3次操作移动筹码3，在第4次操作移动筹码1，在第5次操作移动筹码2，依此类推。如果没有相邻的白色顶点，则游戏结束。求你能执行的最大操作次数。

输入输出格式：
输入格式：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——树的顶点数。
- 接下来的n-1行每行包含两个整数v和u（1≤v,u≤n）——边的描述。给定的边形成一个树。
- 下一行包含一个整数k（1≤k≤n）——筹码的数量。
- 下一行包含k个整数a1, a2, ..., ak（1≤ai≤n）——有筹码的顶点。所有ai都是不同的。
- 所有测试用例的n之和不超过2×10^5。

输出格式：
- 对于每个测试用例，输出一个整数——你能执行的最大操作次数。

输入输出样例：
输入样例 #1：
```
5
5
1 2
2 3
3 4
4 5
1
3
5
1 2
2 3
3 4
4 5
2
1 2
5
1 2
2 3
3 4
4 5
2
2 1
6
1 2
1 3
2 4
2 5
3 6
3
1 4 6
1
1
1
```
输出样例 #1：
```
2
0
1
2
0
```题目大意： 一个包含n个顶点的树，有k个筹码，分别放在顶点a1, a2, ..., ak上。所有ai最初都是黑色的，其余顶点是白色的。你将进行一系列操作（可能为零），在第i次操作（1为起始）时，你将第((i - 1) mod k + 1)个筹码从当前位置移动到一个相邻的白色顶点，并将该顶点染成黑色。如果k=3，则在第1次操作移动筹码1，在第2次操作移动筹码2，在第3次操作移动筹码3，在第4次操作移动筹码1，在第5次操作移动筹码2，依此类推。如果没有相邻的白色顶点，则游戏结束。求你能执行的最大操作次数。 输入输出格式： 输入格式： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——树的顶点数。 - 接下来的n-1行每行包含两个整数v和u（1≤v,u≤n）——边的描述。给定的边形成一个树。 - 下一行包含一个整数k（1≤k≤n）——筹码的数量。 - 下一行包含k个整数a1, a2, ..., ak（1≤ai≤n）——有筹码的顶点。所有ai都是不同的。 - 所有测试用例的n之和不超过2×10^5。 输出格式： - 对于每个测试用例，输出一个整数——你能执行的最大操作次数。 输入输出样例： 输入样例 #1： ``` 5 5 1 2 2 3 3 4 4 5 1 3 5 1 2 2 3 3 4 4 5 2 1 2 5 1 2 2 3 3 4 4 5 2 2 1 6 1 2 1 3 2 4 2 5 3 6 3 1 4 6 1 1 1 ``` 输出样例 #1： ``` 2 0 1 2 0 ```