2008. The Deepest Node Above Both
A tree with n nodes is given as n - 1 edges, rooted at node 1. For each of
q pairs u v, print their LOWEST COMMON ANCESTOR: the deepest node that is an
ancestor of both.
A node counts as an ancestor of itself, so the answer for u v where u is an
ancestor of v is u.
``` edges: 1-2 1-3 2-4 2-5
4 and 5 -> 2 both hang off 2 4 and 3 -> 1 their paths only meet at the root 2 and 4 -> 2 2 is an ancestor of 4, and of itself ```
## What most people try first
Mark every ancestor of u, then walk up from v until you hit a mark. It is
correct and costs the depth per question, so a path-shaped tree gives
4 * 10^10 steps at the limits. Clearing the marks between questions costs the
same again unless you are careful.
## Lift the deeper one, then lift together
Two steps, both using the up[j][v] table of problem 2007.
First make the depths equal: if u is deeper, jump it up by
depth[u] - depth[v] using the binary representation of that difference. If the
two are now the same node, that node is the answer, which is exactly the
ancestor-of-itself case.
Otherwise lift BOTH by the largest jump that keeps them apart, from the biggest power of two downwards:
for j from high down to 0:
if up[j][u] != up[j][v]:
u = up[j][u]; v = up[j][v]
answer = parent of u
## Why the answer is the parent, not u
The loop moves only when the two ancestors still differ, so it never jumps past
the meeting point. When it finishes, u and v are the deepest pair that are
still different, which makes their common parent the deepest shared ancestor.
Jumping while they are EQUAL would be the error: up[j][u] == up[j][v] means
that jump has already passed the answer or landed on it, and taking it loses the
information about how much further down the true meeting point is.
## The boundary
Asking for u and u must answer u. The depth-equalising step makes them the
same node immediately and the second loop never runs, which is why that case
needs no separate handling if the equality check sits between the two steps.
## Cost
O(n log n) to build, O(log n) per question, at most 18 jumps for each of the
two phases at n = 2 * 10^5.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ u, v ≤ n` - the `n - 1` edges always form a tree, and it is rooted at node 1
Input
The first line contains two integers n and q.
Each of the next n - 1 lines contains two integers u and v, an edge of the tree.
Each of the next q lines contains two integers u and v.
Output
Print one integer on its own line for each pair: the number of their lowest common ancestor, where a node counts as an ancestor of itself.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.