Game On Tree
Contest: Educational Codeforces Round 98 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, dfs and similar, greedy, trees

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.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
5
2 4
3 1
3 4
3 5
2
4 5

Example output:
2 1 2 0 0

Example input:
8
4 1
8 4
4 5
6 4
2 5
4 3
1 7
3
2 8 3

Example output:
3 0 0 3 1 2 3 0

Editorial:
This task was inspired by an older edu task and another task proposed by RockyB.
Let's learn to solve the problem for at least one starting vertex for Alice. Let this vertex be $$$v$$$. In general, Alice's strategy is basically this: run to some vertex $$$u$$$ as fast as possible and stay in it until Bob reaches $$$u$$$. Hesitation on a way to this vertex won't be optimal. Visiting the same vertex multiple times won't as well. I guess that can be proven more formally by analyzing the set of possible solutions after each move.
What properties should vertex $$$u$$$ have for Alice to be able to escape to it? There shouldn't be a way for Bob to catch her midway. However, it's not necessary to check any midway intersections. If Bob can catch her anywhere on a path, she can also follow her to the end (by moving the same path) and catch her at the destination. Thus, this vertex $$$u$$$ should be further from any Bob's chips than from $$$v$$$.
So you can precalculate the distance to the closest Bob's chip $$$d_w$$$ to each vertex $$$w$$$. Just push all chips to a queue and run a bfs.
We've learned to solve the problem in $$$O(n)$$$ for each vertex $$$v$$$. Just iterate over all vertices $$$u$$$ and take the maximum of $$$d_u$$$ over such of them that have $$$d_u$$$ greater than the distance from $$$v$$$ to $$$u$$$.
Now the solution can go two ways. You can stop thinking here and obtain an $$$O(n \log^2 n)$$$ one or think more and get an $$$O(n \log n)$$$.
The first one goes like that. Notice that the function $$$f(v, x)$$$ if the Alice can make at least $$$x$$$ moves from vertex $$$v$$$ is monotonous in regard to $$$x$$$. So we can binary search the answer. The check query transforms to the following. Consider all vertices with distance less or equal to $$$x$$$ from $$$v$$$. There should exist at least one vertex $$$u$$$ with value $$$d_u>x$$$ for the check to return true. So at least the maximum value of them should be greater than $$$x$$$.
That is basically a centroid exercise. Let each centroid store such an array $$$val$$$ that $$$val_i$$$ is the maximum value of $$$d_u$$$ over all such $$$u$$$ that belong to this centroid's subgraph and are no further than $$$i$$$ distance from the centroid. That array can be constructed in $$$O(n \log n)$$$ for all centroids in total. You can easily see that the length of this array doesn't exceed the number of vertices in the subgraph of the corresponding centroid that is $$$O(n \log n)$$$ be definition.
For the query iterate over all centroids $$$v$$$ belongs to and check the value from some cell of each one's $$$val$$$ array.
For the second solution let's reverse the problem. Consider the vertex $$$u$$$ Alice escapes to. If there is a starting vertex $$$v$$$ no further than $$$d_u - 1$$$ from it, then the answer for $$$v$$$ can be updated with $$$d_u$$$. So we can update the subgraph of vertices with distance no more than $$$d_u - 1$$$ with the maximum of their current answer and $$$d_u$$$.
The solution will be almost the same centroid. Iterate over all centroids $$$u$$$ belongs to and write $$$d_u$$$ into the cell $$$i$$$ of each one's array $$$val$$$, where $$$i$$$ is the distance from $$$u$$$ to this centroid. Then build an array of prefix maximums over this array. Finally, for each $$$v$$$ collect the best answer over all centroids $$$v$$$ belongs to.
Overall complexity: $$$O(n \log^2 n)$$$ or $$$O(n \log n)$$$.