Game on Tree (Hard)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 1900
Tags: dfs and similar, dp, games, trees

This is the hard version of the problem. The only difference in this version is the constraint on $$$t$$$.

Ron and Hermione are playing a game on a tree of $$$n$$$ nodes that are initially inactive. The game consists of $$$t$$$ rounds, each of which starts with a stone on exactly one node, which is considered as activated. A move consists of picking an inactive neighbor of the node with a stone on it and moving the stone there (thus activating this neighbor). Ron makes the first move, after which he alternates with Hermione until no valid move is available. The player that cannot make a move loses the round. If both players play optimally, who wins each round of this game?

Note that all the rounds are played with the same tree; only the starting node changes. Moreover, after each round, all active nodes are considered inactive again.

Input format:
The first line contains integers $$$n$$$ ($$$2 \leq n \leq 2\times 10^5$$$), $$$t$$$ ($$$1 \leq t \leq n$$$), the number of nodes in the tree and the number of rounds, respectively.

The next $$$n-1$$$ lines contain two integers $$$1 \leq u, v \leq n$$$ each, corresponding to an edge of the tree.

The next line contains $$$t$$$ integers $$$1 \leq u_1 , \dots , u_t \leq n$$$, corresponding to the node where the stone is initially put.

Output format:
The output consists of $$$t$$$ lines, each line being either "Ron" or "Hermione".

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

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

Example output:
Ron
Ron

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

Example output:
Hermione
Ron
Hermione

Editorial:
Repeating the previous solution for each $$$u_i$$$ is too slow as it gives a $$$O(n.t)$$$ solution.  Instead, we will reuse the computations we did when assigning losing/winning positions. We do so using the re-rooting technique. Let's first compute the positions of the nodes in the tree rooted at 0. We will now find in linear time the position of each node if the tree was rooted at that node.  Let $$$v$$$ be the current root (initially $$$v=0$$$) and let $$$w$$$ be a child of $$$v$$$. Let $$$T$$$ be the initial tree and $$$T'$$$ be the tree re-rooted at $$$w$$$. We know the positions of all nodes in $$$T$$$, and we want to find the position of nodes in $$$T'$$$. First note that only the positions of $$$v$$$ and $$$w$$$ may differ because the subtrees of all the other nodes remain unchanged.   If $$$v$$$ has a child other than $$$w$$$ which corresponds to a losing position (in $$$T)$$$, then $$$v$$$ is a winning position in $$$T'$$$. If $$$v$$$ has no losing child or has exactly one losing child which is $$$w$$$ (in $$$T)$$$, then it is a losing position in $$$T'$$$. Similarly, if $$$w$$$ has some child that is a losing position (including $$$v$$$ in $$$T'$$$), then it is a winning position otherwise it is a losing position in $$$T'$$$. The above checks can be done in constant time by counting the number of losing children before the recursive calls (this count also needs to be maintained before recurring on a subtree). We thus recur on $$$W$$$ and repeat. Once the recursive call is over, we backtrack our changes before recurring on a different child of $$$v$$$.
At the beginning of each recursive call, we know whether Ron or Hermione wins if the game started at that node so we can answer all the queries by doing linear-time pre-processing.