Game On Tree

题意翻译

### 题意描述 Alice和Bob在玩一个游戏。他们有一棵由$n$个结点组成的树。一开始，Bob有$k$个卡片，其中第$i$个卡片位于结点$a_i$（注意：所有的结点都是唯一的）。在游戏开始之前，Alice将在这棵树的一个结点上放置一个卡片。\ 这个游戏由一些回合组成。每个回合都将有以下事件发生（完全按照以下顺序）： 1. Alice可以把她的卡片移到相邻的结点，或者不移动； 2. 对于Bob的每一张卡片，他可以把这张卡片移到相邻的结点，或者不移动。注意：每个卡片的选择都是独立的。 当Alice的卡片与Bob的任意一张（或多张）卡片在同一结点时，游戏结束。（Bob自己的多张卡片可以置于同一结点上）\ Alice希望游戏回合越多越好，Bob则相反。\ 如果某回合中间游戏结束（即Alice把卡片移到了有Bob卡片的结点上），这回合依然算入总回合数。\ 对于每个结点，计算Alice一开始将卡片放在该结点时游戏将持续的回合数。 ### 输入格式 第$1$行：整数$n$\ 第$2$至第$n$行：两个整数$a_i$,$b_i$：这个树的一条边所连接的两个结点。\ 第$n+1$行：整数$k$\ 最后一行：$k$个整数，表示Bob的每张卡片的位置。 ### 输出格式 一行$n$个整数，以空格分隔。第$i$个整数为Alice一开始将卡片放在第i个结点时游戏将持续的回合数。如果Alice一开始就把她的卡片放在Bob的卡片上面，游戏立即结束，视为经过了$0$个回合（即输出$0$）

题目描述

Alice and Bob are playing a game. They have a tree consisting of $ n $ vertices. Initially, Bob has $ k $ chips, the $ i $ -th chip is located in the vertex $ a_i $ (all these vertices are unique). Before the game starts, Alice will place a chip into one of the vertices of the tree. The game consists of turns. Each turn, the following events happen (sequentially, exactly in the following order): 1. Alice either moves her chip to an adjacent vertex or doesn't move it; 2. for each Bob's chip, he either moves it to an adjacent vertex or doesn't move it. Note that this choice is done independently for each chip. The game ends when Alice's chip shares the same vertex with one (or multiple) of Bob's chips. Note that Bob's chips may share the same vertex, even though they are in different vertices at the beginning of the game. Alice wants to maximize the number of turns, Bob wants to minimize it. If the game ends in the middle of some turn (Alice moves her chip to a vertex that contains one or multiple Bob's chips), this turn is counted. For each vertex, calculate the number of turns the game will last if Alice places her chip in that vertex.

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree. Then $ n - 1 $ lines follow, each line contains two integers $ u_i $ , $ v_i $ ( $ 1 \le u_i, v_i \le n $ ; $ u_i \ne v_i $ ) that denote the endpoints of an edge. These edges form a tree. The next line contains one integer $ k $ ( $ 1 \le k \le n - 1 $ ) — the number of Bob's chips. The last line contains $ k $ integers $ a_1 $ , $ a_2 $ , ..., $ a_k $ ( $ 1 \le a_i \le n $ ; $ a_i \ne a_j $ if $ i \ne j $ ) — the vertices where the Bob's chips are initially placed.

输出格式

Print $ n $ integers. The $ i $ -th of them should be equal to the number of turns the game will last if Alice initially places her chip in the vertex $ i $ . If one of Bob's chips is already placed in vertex $ i $ , then the answer for vertex $ i $ is $ 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