← 返回题目列表

Codeforces · 1452/G

G. 树上的游戏

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

Alice 和 Bob 正在玩游戏。他们有一棵由 $$$n$$$ 个顶点组成的树。最初,Bob 有 $$$k$$$ 个筹码,第 $$$i$$$ 个筹码位于顶点 $$$a_i$$$(所有这些顶点都是唯一的)。在游戏开始之前,爱丽丝会将一个芯片放入树的一个顶点中。

游戏由回合组成。每回合,都会发生以下事件(顺序地,完全按照以下顺序):

1. Alice 要么将她的筹码移动到相邻顶点,要么不移动它;
2. 对于 Bob 的每个筹码,他要么将其移动到相邻顶点,要么不移动它。请注意,此选择是针对每个芯片独立完成的。

当 Alice 的筹码与 Bob 的一个(或多个)筹码共享同一顶点时,游戏结束。请注意,鲍勃的筹码可能共享相同的顶点,即使它们在游戏开始时位于不同的顶点。

Alice 想要最大化轮数,Bob 想要最小化它。如果游戏在某个回合中间结束(爱丽丝将她的筹码移动到包含一个或多个鲍勃筹码的顶点),则该回合被计算在内。

对于每个顶点,计算如果 Alice 将筹码放在该顶点,游戏将持续的回合数。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。

接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) 表示边的端点。这些边形成一棵树。

下一行包含一个整数 $$$k$$$ ($$$1 \le k \le n - 1$$$) — Bob 的筹码数量。

最后一行包含 $$$k$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ ($$$1 \le a_i \le n$$$; $$$a_i \ne a_j$$$ if $$$i \ne j$$$) — Bob 筹码最初放置的顶点。

输出

打印 $$$n$$$ 整数。如果 Alice 最初将筹码放在顶点 $$$i$$$ 上,则其中的第 $$$i$$$ 应该等于游戏将持续的回合数。如果 Bob 的一个筹码已放置在顶点 $$$i$$$ 中,则顶点 $$$i$$$ 的答案为 $$$0$$$。

示例

输入 #1

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

输出 #1

2 1 2 0 0

输入 #2

8
4 1
8 4
4 5
6 4
2 5
4 3
1 7
3
2 8 3

输出 #2

3 0 0 3 1 2 3 0

输入 #3

10
2 5
4 3
7 3
7 2
5 8
3 6
8 10
7 9
7 1
4
10 6 9 1

输出 #3

0 2 2 2 2 0 2 2 0 0