← 返回题目列表

Codeforces · 1795/F

F. 阻塞芯片

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

给你一棵树,由 $$$n$$$ 个顶点组成。有 $$$k$$$ 个筹码,放置在顶点 $$$a_1、a_2、\dots、a_k$$$ 中。所有 $$$a_i$$$ 都是不同的。顶点 $$$a_1, a_2, \dots, a_k$$$ 最初被涂成黑色。其余的顶点是白色的。

您将要玩一个游戏,您将执行一些动作(可能是零)。在第 $$$i$$$ 次移动($$$1$$$ 索引)中,您将把 $$$((i - 1) \bmod k + 1)$$$-st 芯片从当前顶点移动到相邻的白色顶点,并将该顶点着色为黑色。因此,如果 $$$k=3$$$,则您在移动 $$$1$$$ 时移动筹码 $$$1$$$,在移动 $$$2$$$ 时移动筹码 $$$2$$$,在移动 $$$3$$$ 时移动筹码 $$$3$$$,在移动 $$$4$$$ 时移动筹码 $$$1$$$,在移动 $$$5$$$ 时移动筹码 $$$2$$$,依此类推。如果没有相邻的白色顶点,则游戏结束。

您最多可以执行多少步?

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 树的顶点数。

接下来的 $$$n - 1$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$) - 边的描述。给定的边形成一棵树。

下一行包含一个整数 $$$k$$$ ($$$1 \le k \le n$$$) — 芯片数量。

下一行包含 $$$k$$$ 整数 $$$a_1, a_2, \dots, a_k$$$ ($$$1 \le a_i \le n$$$) — 带芯片的顶点。所有 $$$a_i$$$ 都是不同的。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 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