CF1795F.Blocking Chips
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a tree, consisting of n vertices. There are k chips, placed in vertices a1,a2,…,ak . All ai are distinct. Vertices a1,a2,…,ak 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)modk+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≤t≤104 ) — the number of testcases.
The first line of each testcase contains a single integer n ( 1≤n≤2⋅105 ) — the number of vertices of the tree.
Each of the next n−1 lines contains two integers v and u ( 1≤v,u≤n ) — the descriptions of the edges. The given edges form a tree.
The next line contains a single integer k ( 1≤k≤n ) — the number of chips.
The next line contains k integers a1,a2,…,ak ( 1≤ai≤n ) — the vertices with the chips. All ai are distinct.
The sum of n over all testcases doesn't exceed 2⋅105 .
输出格式
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