== Solution

This paragraph provides a formal proof of correctness. The next one provides the details about complexity and implementation.

Let $P(u, v)$ denote the path between $u$ and $v$.

*Lemma 1:* When removing all edges with an endpoint $P(u, v)$, we split the tree in a rooted forest $cal(F)_(u,v)$. If one token moves from $u$ to $v$,
then the distance between $u$, $v$ must be $K$ at least once, where $K$ is defined to be the depth of the deepest tree in $cal(F)$.

_Proof:_ Let $pi(w)$ be the closest node to $w$ which is also inside $P(u,v)$. Consider $pi(x)$ and $pi(y)$ where $x$ and $y$ are the positions of the two tokens.
As the two tokens move, there must be a moment when $pi(x) = pi(y)$ (since $pi(x)$ and $pi(y)$ behave like normal tokens on a line).\
When this happens for the first time, one of $x$ and $y$ must be on the path $P(u, v)$, since if this had not been the case, $pi(x)$ and $pi(y)$ would not have changed
with the last move.\
Therefore, one of the two tokens is on the path $P(u,v)$ and the other can be at most $K$ edges away from it (since $K$ is the maximum depth in $cal(F)_(u,v)$). #h(1fr) $qed$

*Lemma 2:* When removing all edges with an endpoint at $w$, we split the tree in a rooted forest $cal(G)_w$. Let $S_3(w)$ be the third greatest depth of a subtree in $cal(G)_w$ and $0$ if $cal(G)_w$ has less than $3$ trees in it.\
Then, the answer to *any query* can be at most $max_(w=0)^(N-1)S_3(w)$.

_Proof:_ Let $w$ be the node which maximizes $S_3(w)$. Consider the forest $cal(G)_w$ and the three deepest trees $cal(T)_1$, $cal(T)_2$ and $cal(T)_3$ inside of it.
Then, choose some leaves $ell_1 in cal(T)_1$, $ell_2 in cal(T)_2$ and $ell_3 in cal(T)_3$ such that the depths of $ell_1$, $ell_2$ and $ell_3$ are maximal.\
Consider the path $P(ell_1, ell_2)$. If we show that all trees in $cal(F)_(ell_1, ell_2)$ are not deeper than $cal(T)_3$, then by Lemma 1 we are done.\
This is the same as showing that any tree in $cal(F)_(ell_1, ell_2)$ cannot be any of the two deepest subtrees of a node in $P(ell_1,ell_2)$, since $cal(T)_3$ is by definition
deeper than all third (or further) greatest subtrees.\
Let $Gamma$ be any tree in $cal(F)_(ell_1, ell_2)$ and $gamma$ the node in $P(ell_1, ell_2)$ it would be attached to. $gamma$ can be assumed not to be $w$, since we know that
when $gamma = w$ the deepest subtree is precisely $cal(T)_3$. Therefore, exactly one of the paths $P(ell_1, gamma)$, $P(ell_2, gamma)$ contains $w$.
Without loss of generality, assume $w in.not P(ell_1, gamma)$.\
If the depth of $Gamma$ were greater than $d(ell_1, gamma)$, then $ell_1$ would not be of maximal depth in $cal(T)_1$. So the tree containing $ell_1$ must be at least as deep as $Gamma$.
Let us now assume the tree $Z in cal(G)_gamma$ containing $ell_2$ is shallower than $Gamma$. Then, $Z$ would not be shallower than $S_3(gamma)$, since we would have already found two trees of $cal(G)_gamma$ not shallower than it. But then, since $Z$ is deeper than $cal(T)_2$, it would also be deeper than $cal(T)_3$. Thus, $w$ would not maximize $S_3(w)$, which is absurd.
#h(1fr) $qed$

Let $L$ be the maximum value assumed by $S_3$.

Let $d(x, y)$ denote the distance of $x$ and $y$ in the tree.\
Let $A(x, y)$ denote the answer to the query with nodes $x$ and $y$.

Now we assume we rooted the tree at the node which maximizes $S_3$. We now have a notion of "depth", "lowest common ancestor" and "subtree".

Let $"dep"(u)$ be the depth of $u$.\
Let $"lca"(u, v)$ be the lowest common ancestor of $u$ and $v$.

*Lemma 3:* $A(x,y) <= d(x,y)$.

_Proof:_ In the first moment of the patrol the tokens are exactly at distance $d(x,y)$. #h(1fr) $qed$

*Lemma 4:* Let $X'$ and $Y'$ be arbitrary leaves in the subtrees of $X$ and $Y$ respectively. Then, $A(X,Y) <= A(X',Y')$.

_Proof:_ We can move the tokens from $(X', Y')$ to $(X, Y)$, perform the optimal patrol $cal(P)$ for starting nodes $(X, Y)$ and then move
the tokens back to $(X', Y')$. When we are not performing $cal(P)$ the tokens are at least $d(x, y)$ away from each other, but since $d(x, y) >= A(x, y)$ this
means the minimal distance is achieved while performing $cal(P)$.
Therefore we have a patrol starting at $(X', Y')$ which scores at least as much as $cal(P)$. Thus, $A(X,Y) <= A(X',Y')$ #h(1fr) $qed$

*Lemma 5:* Let $X'$ and $Y'$ be arbitrary leaves in the subtrees of $X$ and $Y$ respectively. Then, $A(X,Y) = min(A(X',Y'), d(X,Y))$

_Proof:_ We can move the tokens from $(X, Y)$ to $(X', Y')$, then perform the optimal patrol $cal(P)$ from nodes $(X',Y')$ and then move the token back to $(X,Y)$.
The tokens never come closer than $d(X,Y)$ or $A(X',Y')$ during this patrol, and we have already proven none of these two can be exceeded. #h(1fr) $qed$

We can assume without loss of generality that $X$ and $Y$ are leaves.

*Lemma 6:* Define the _pre-score_ $p(cal(P))$ of a patrol to be the minimum distance between the two tokens up until the first moment when one of the two tokens is at $"lca"(X,Y)$.
Let $p_"max"$ be the maximum value of $p$ as $cal(P)$ varies among all valid patrols.
Then, $A(X,Y)=min(p_"max", L)$.

_Proof:_ We can construct a patrol with score $min(p_"max", D)$. Since these are both obvious upper bounds, the construction suffices.
Let $cal(T)_1$, $cal(T)_2, cal(T)_3$ and $ell_1$, $ell_2$, $ell_3$ be defined as in the proof of Lemma 2.\
Let $(i,j,k)$ be a permutation of $(1,2,3)$ such that neither $X$ nor $Y$ are in $cal(T)_k$.
The patrol is constructed as follows:
+ We first move $X$ and $Y$ using a patrol with maximum pre-score until either of the tokens is at $"lca"(X,Y)$.
+ We move the token at the lowest common ancestor to $ell_k$. Doing this, the distance between the tokens is increasing and therefore greater than $p_"max"$.
+ We move the other token through all the nodes except those in $cal(T)_k$, then we move it to $ell_j$. Doing this, the distance is always at least $D$.
+ We move the token at $ell_k$ through all the nodes except those in $cal(T)_j$, then we move it to $ell_i$. Doing this, the distance is always at least $D$.
+ We move the token at $ell_j$ through all the nodes except those in $cal(T)_i$, then we move it to $ell_k$. Doing this, the distance is always at least $D$.
+ We move the token at $ell_i$ through all the nodes except those in $cal(T)_k$. Doing this, the distance is always at least $D$.
+ We repeat everything we did so far in reverse, thus restoring the initial position of the tokens.
#h(1fr) $qed$

We now define a _pre-patrol_ as a sequence of moves which ends when one of the two tokens reaches $"lca"(X,Y)$.

*Lemma 7:* Let $M(w)$ be the deepest node in the subtree rooted at $w$. Then, the following algorithm finds a list of pre-patrols one of which must have maximum pre-score.

*Algorithm 1:*
We are going to assume that $"lca"(X,Y) in.not {X, Y}$ since otherwise it is obvious that $p_"max" = d(X,Y)$.

+ Let $xi$ and $eta$ be at any moment the position of the two tokens (initially $xi=X$ and $eta=Y$).
+ Create an empty pre-patrol $cal(P)$.
+ Create an empty list of candidate patrols $cal(C)$.
+ Repeat the following:
  + Add the pre-patrol $cal(P)'$ obtained by moving the token at the shallowest of $xi$ and $eta$ to $"lca"(X,Y)$ to the list $cal(C)$.
  + Let $xi_0$ be the lowest ancestor of $xi$ such that $"dep"(M(xi_0))>"dep"(xi)$.
  + Let $eta_0$ be the lowest ancestor of $eta$ such that $"dep"(M(eta_0))>"dep"(eta)$.
  + If both $xi_0$ and $eta_0$ are either non existent or not lower than $"lca"(X,Y)$, stop iterating.
  + If $xi_0$ exists, and either $eta_0$ does not exist or $d(xi,xi_0) < d(eta,eta_0)$:
    + Extend $cal(P)$ by moving the token at $xi$ to the deepest node in the subtree rooted at $xi_0$ using the simple path between the two.
  + Otherwise:
    + Extend $cal(P)$ by moving the token $eta$ to the deepest node in the subtree rooted at $eta_0$ using the simple path bewteen the two.
+ The list $cal(C)$ must contain a pre-patrol with maximal pre-score.

_Proof:_
When the tokens are at $(xi,eta)$ one of two things will happen:
+ Either it is optimal to move one of the tokens to the lowest common ancestor of $X$ and $Y$,
  in which case it is obvious that the shallowest is the one that should be moved.
+ Or it is not. In this case, one of the two tokens must reach a depth greater than its current one.
  We may assume we move each token in _actions_, with each action being a sequence of moves moving a token from a leaf to another of greater depth, until we are in the first case.\
  This is because, if we had fixed the maximum distance we might accept during our patrol, if one of the two tokens does not lower its depth,
  the other one will be able to move to at most the same nodes as if no move had occurred.\
  This is why we have to move either the first token to $xi_0$ or the second one to $eta_0$. Then we can prioritize the move to the deepest of the two subtrees
  because performing both moves in this order is never worse than performing the move to the shallowest subtree on its own.
  If it is optimal to go even higher than $xi_0$ or $eta_0$, this will be found in later iterations.
#h(1fr) $qed$

== Implementation

We can implement the solution proven above in $cal(O)(N log N + Q sqrt(N))$ time and $O(N log N)$ memory.

First, the node which maximizes $S_3$ can be found in $cal(O)(N log N)$ by dynamic programming and rerooting (which is done by the lambda functions `calc_size` and `reroot` in my implementation).

Then, we can find for each node its lower ancestor with a deeper subtree than itself using binary lifting in $cal(O)(N log N)$ (which is done by the lambda function `low_anc` in my implementation).

Last, we will need a standard data structure to find the lowest common ancestor of two nodes and an arbitrary leaf in the subtree of a node.
For this purpose my implementation uses a sparse table on the Euler tour of the tree.

For the queries, we just implement Algorithm 1 as described above. Since for each of the two starting nodes we are visiting distinct subtrees of increasing depth
the loop must end after at most $cal(O)(sqrt(N))$ iterations.

== Subtasks
#[
  #set heading(numbering: (.., x) => sym.bullet)

  === The tree is a line
  This subtask should be solvable by the great majority of the contestants. Since the two tokens must overlap at least once, the answer is $0$ for all possible queries.

  === The tree is a star
  This is another easy subtask. The answer is $0$ if $X=Y$ and $1$ otherwise.

  === $X$ and $Y$ maximize the answer
  It is easy to show that it is possible to show that the bound $max_(w=0)^(N-1)S_3(w)$ can be achieved with starting nodes $ell_1$ and $ell_2$.
  Therefore, for this subtask it is enough to compute the maximum value of $S_3$ and then return it as the answer to all queries.

  === $N, Q <= 200$ (`dijkstra.cpp`)
  We can run Dijkstra's algorithm on the pairs of nodes $(u,v)$ where
  - neighbours of $(u,v)$ are of the form $(u,w)$ or $(z,v)$ where $w$ is a neighbour of $v$ and $z$ is a neighbour of $u$.
  - the cost of an edge $((u,v),(w,x))$ is $"min"(d(u,v),d(w,x))$.
  - the cost of a path is the minimum weight among all of its edges.

  We stop the algorithm when we have visited at least one node of the form $(k,x)$ and one of the form $(x,k)$ for each $0 <= k < N$.

  The complexity is $O(N^2 log N)$ for each query.

  === $N <= 1000$ (`precalc.cpp`)
  Let's keep the same graph as before. This time however we will precompute the answers to all possible queries.
  
  We build a DSU on the graph and add edges to it from the heaviest to the lightest.
  When a connected component has at least one node of the form $(k,x)$ and one for the form $(x,k)$ for each $0 <= k < N$, we know that
  the answer for all of its nodes is the weight of the last added edge.

  If we merge components using the small to large technique, we achieve a complexity of $cal(O)(N^2 log N)$ for the precomputation.

  === $Q <= 1000$
  This subtask is intended to award solution which find the lowest ancestor with a deep enough subtree in a suboptimal way.
  This could be either:
  - Not precomputing the values, but still using binary lifting, thus obtaining $O(sqrt(N) log N)$ complexity per query.
  - Naively iterating on the ancestors, which gives $O(N)$ complexity per query.

  === $N, Q <= 10^5$ (`solution.cpp`)
  The complete solution.
]
]