CF1795F Blocking Chips

给定一棵包含 $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)$ 个棋子从当前顶点移动到一个相邻的白色顶点，并将该顶点染为黑色。因此，如果 $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 \times 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 \times 10^5$。

对于每个测试用例，输出一个整数，表示你最多能进行的操作次数。

由 ChatGPT 4.1 翻译