Observations

The park can be modeled as a tree, where claerings are nodes and pathways are edges.

It is also easy to see that the tagger's optimal strategy is to always move to the unique node which brings them closer to the runner. It is unique due to the property of unique paths on a tree.

The runner's optimal strategy is slightly more complicated. Consider rooting the tree at the tagger's starting position. We can split the runner's strategy into two phases:

1. Approach:

   • The runner moves up the tree (i.e. towards the tagger) until they reach some node ~x~.
   • It is possible that the ~x~ is simply the runner's starting node and the runner does not move up the tree at all.

2. Flee:

   • The runner moves down the tree towards the deepest node in the subtree of node ~x~.
   • If there are multiple deepest nodes, any one of them will suffice.
   • If this deepest node is reached, then simply stay still at this node until caught by the tagger.

The Approach phase is necessary in some scenarios to allow the runner to reach deeper nodes from the subtree of node ~x~ (i.e. the benefit of travelling up the tree to be able to reach a deeper node may outweigh the deficit of going closer to the tagger), and the Flee phase is intuitively optimal afterwards.

Note that in the Approach phase, the runner has a limit of far they can move up before the tagger tags them from above. Additionally, if the Turtle is the tagger and the Rabbit is the runner, the Rabbit will never be caught during the Flee phase and will always be able to reach the deepest node in the subtree of ~x~. On the other hand, if the Turtle is the runner and the Rabbit is the tagger, it is possible for the Turtle to be caught during the Flee phase before reaching the deepest node.

Subtask 1

In this subtask, the Turtle is always the tagger and always begins at node ~1~. The Rabbit is always the runner and queries only vary by where the Rabbit begins.

Using our observations from above, we can first compute the distance to the deepest nodes in the subtree of each node when the tree is rooted at node ~1~. This can be done with the simple recurrence of ~dp[i] = \max\{dp[j] + 1\}~, where ~j~ is a child of node ~i~. For any nodes ~i~ with no children, ~dp[i] = 0~.

This allows us to find the deepest node that the Rabbit can run to in the Flee phase for any node ~x~ that the Rabbit stops at from the Approach phase.

From here, we observe that it is always optimal for the Rabbit to run as far up the tree as possible without being caught by the Turtle in the Approach phase, since it will always be able to outrun the Turtle in the Flee phase and ~dp[i] > dp[j]~ if ~i~ is an ancestor of ~j~. In other words, if the Rabbit can stop the Approach phase at node ~i~ or at node ~j~ where ~i~ is an ancestor of ~j~, then the deepest node in the subtree of node ~i~ is at least as deep as the deepest node in the subtree of node ~j~.

To find the highest node ~x~ which the Rabbit can run to without being caught by the Turtle, we can use binary lifting to find the ancestor of the Rabbit's starting node which is ~2/3~ of the way to the root.

To compute exactly how long the game lasts, we multiply the depth of the deepest node in the subtree of node ~x~ (i.e. ~dp[x]~) by ~2~, since it takes the Turtle two seconds to travel down one edge in the tree.

Time Complexity: ~\mathcal{O}((N+Q) \log N)~

Subtask 2

In this subtask, the Turtle is still always the tagger but can have an arbitrary starting node.

This motivates a generalization of our Subtask 1 solution where any node can be treated as the root of the tree.

We can still find the node ~x~ which is ~2/3~ of way along the path from the Rabbit's starting node to the Turtle's starting node using ~k^{th}~ ancestor and LCA primitives.

It remains to be able to calculate the deepest node in the subtree of an arbitrary node ~x~ if the tree were rooted at an arbitrary node, the Turtle's starting node.

Consider fixing the node ~x~ and varying the Turtle's starting node (i.e. the root of the tree). The subtree of node ~x~ can be thought of as any part of the tree which can be reached without moving in the direction of the root. In other words, the subtree of node ~x~ can be thought of as the component of tree reachable from ~x~ if the unique edge connected to node ~x~ on the path from node ~x~ to the root is deleted.

Thus, if we have some method to determine the furthest node from each node ~x~ for each possible one of its edges being deleted, this will be sufficient information to calculate distance in the Flee phase.

In fact, we only need to know the distancee to the furthest node with no restrictions, the direction traveled to get to this furthest node, and furthest node when this direction is restricted. This is because when any other direction is restricted, the furthest node with no restrictions will remain the furthest. If and only if the direction of the furthest node itself is restricted will the Rabbit have to run to the second furthest node in another direction.

To preprocess these values, we can use rerooting dynamic programming. It suffices to maintain the directions of the first and second furthest nodes and their distances. Details are left as an exercise to the reader.

When computing the furthest node from ~x~ which does not travel in the direction of the Turtle's starting node, we check if the direction of the furthest node from ~x~ is towards the Turtle using tree primitives. If so, the use the preprocessed distance to the second furthest node. If not, use the preprocessed distance to the furthest node.

Note: There likely exists a solution which uses diameter endpoints to avoid using the tree rerooting technique, since the furthest node from any node in a tree is one of the diameter endpoints. The second furthest when the direction towards the diameter endpoints are banned can probably be found by running the Subtask 1 dynamic programming on the tree rooted at the diameter endpoints. However, I am too lazy to look into this further and provide this solution instead.

Time Complexity: ~\mathcal{O}((N+Q)\log N)~

Subtask 3

In this subtask, it is possible for the Rabbit to be the tagger and the Turtle to be the runner.

It is no longer obvious which node ~x~ the Turtle should stop at in the Approach phase, since it is not guarenteed that the Turtle will be able to run all the way to the deepest node in the subtree of ~x~ without being caught by the Rabbit earlier.

Let us try to understand the exact time the game will last for a given stopping node ~x~ from the Approach phase.

• Let ~d~ be the distance between the starting node of the Turtle and the starting node of the Rabbit.
• Let ~a~ be the distance between the starting node of the Turtle and node ~x~ (i.e. how far the Turtle approaches the Rabbit).
• Let ~F~ be the distance to the furthest node reachable from the subtree of node ~x~ when the tree is rooted at the starting node of the Rabbit (computable via method described in Subtask 2).

The game will last ~\min\left((d-a)+F, 2a + 2(d - 3a) \right)~ seconds. The first term in the ~\min~ function corresponds to the time it takes for the Rabbit to run to the furthest node in the subtree of node ~x~ when the tree is rooted at the Rabbit's starting node, and the second term corresponds to the time it takes for the Rabbit to close the initial distance between it and the Turtle, taking into account the time when the Turtle and Rabbit are running towards each other in the Turtle's Approach phase.

Observe that ~(d-a)+F~ is nondecreasing as ~x~ gets closer to the Rabbit (already known in Subtask 2), while ~2a + 2(d - 3a)~ is strictly decreasing as ~x~ gets closer to the Rabbit. Thus, to maximize the minimum of these two functions, we can binary search for their intersection.

Time Complexity: ~\mathcal{O}((N+Q) \log^2 N)~

Bonus

Author commentary

While only requiring relatively simple tree techniques (rerooting technique, binary lifting, LCA), they are used quite extensively and in ways that are difficult to wrap your head around. I initially thought subtask 2 would involve heavy-light decomposition and some weird data structures to calculate the maximum time for the runner over all possible ~x~ in the Approach phase, so this arguably quite simple binary search was a pleasant surprise.

Note

According to dnialh_ and arvindf232, there exists a ~\mathcal{O}((N+Q) \log N)~ solution, but I do not understand it and will settle with this slower solution.