Blocking Chips
Contest: Educational Codeforces Round 143 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, constructive algorithms, dfs and similar, greedy, trees

You are given a tree, consisting of $$$n$$$ vertices. There are $$$k$$$ chips, placed in vertices $$$a_1, a_2, \dots, a_k$$$. All $$$a_i$$$ are distinct. Vertices $$$a_1, a_2, \dots, a_k$$$ are colored black initially. The remaining vertices are white.

You are going to play a game where you perform some moves (possibly, zero). On the $$$i$$$-th move ($$$1$$$-indexed) you are going to move the $$$((i - 1) \bmod k + 1)$$$-st chip from its current vertex to an adjacent white vertex and color that vertex black. So, if $$$k=3$$$, you move chip $$$1$$$ on move $$$1$$$, chip $$$2$$$ on move $$$2$$$, chip $$$3$$$ on move $$$3$$$, chip $$$1$$$ on move $$$4$$$, chip $$$2$$$ on move $$$5$$$ and so on. If there is no adjacent white vertex, then the game ends.

What's the maximum number of moves you can perform?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices of the tree.

Each of the next $$$n - 1$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$) — the descriptions of the edges. The given edges form a tree.

The next line contains a single integer $$$k$$$ ($$$1 \le k \le n$$$) — the number of chips.

The next line contains $$$k$$$ integers $$$a_1, a_2, \dots, a_k$$$ ($$$1 \le a_i \le n$$$) — the vertices with the chips. All $$$a_i$$$ are distinct.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the maximum number of moves you can perform.

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

Example input:
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

Example output:
2
0
1
2
0

Editorial:
The constraints tell us that the solution should be linear or pretty close to it. Well, in particular, that implies that the solution almost certainly isn't dynamic programming, since we have both $$$n$$$ and $$$k$$$ to care about. Thus, we'll think about something greedy.
When we know the number of move the game will last, we can tell how many steps each chip should make. Well, since the more moves the game last, the more steps each ship makes, the answer is a monotonic function. Let's apply binary search and think if we can check if each chip can make some known number of steps.
A common idea in the problems where you have to do something greedily on a tree is to root the tree arbitrarily and process everything bottom up.
Consider the bottommost chip. If it can move its number of moves downwards, it's always optimal to do that. Since it's the bottommost chip, it can only make things worse for chips above it. And any of them can't pass through the initial vertex of this chip anyway.
If it can't, it has to move to its parent vertex. Let's move it there and deal with this chip later — when it becomes the bottommost again.
If it can't move to its parent, it can't move at all. Thus, the game can't last for this many steps.
Since we only apply either the move which is guaranteed to not interrupt any other moves or the move which is forced, the greedy strategy is correct.
As for implementation details, it's not too tricky. Basically, for each vertex, we should maintain these values:
• if this vertex has been visited;
• the number of steps the chip in this vertex still has to make (if any chip is in this vertex);
• the longest path downwards from this vertex via non-visited vertices.
The second value can be initialized beforehand and pushed to the parent when needed. The rest of them are easily maintained with a single dfs.
Overall complexity: $$$O(n \log n)$$$ per testcase.