LCA (Least Common Ancestor) Problem

[Pavel Nalivaiko]

Can anyone recommend me some problem in UVA's problemset to test my solution to the LCA problem?

[mf]

10938 "Flea circus" can be solved with LCA.

[Pavel Nalivaiko]

10938 "Flea circus" can be solved with LCA.

Thank you, but..
.. how to solve this problem using LCA? In LCA we need a tree with selected root. Even if we precalculate LCA for each node of the tree selected as a root, we still need a O(N) time for every query to decide which node should be selected as a root... I think it will fail with TL.

Each test case could be solved with O(n*n + l) time if we just precalculate distances between the nodes and centre(s) of the pathes between them using DFS...

[mf]

The choice of the root doesn't matter at all! (My solution always uses node #1 as root.)

Here's how how I'm solving each query.

Let:
d(x) denote the length of path between x and the tree's root,
lca(p,q) be the least common ancestor of nodes p,q,
up(x,0) = x,
up(x,k) = parent of up(x,k-1) for k>0. (i.e. up(x,k) is the k-th ancestor of x.)

1. Without the loss of generality, let d(p) >= d(q).
2. The length of the (unique) path between p and q equals: L = d(p) + d(q) - 2*d(lca(p,q)).
Furthermore, this path consists of going d(p)-d(lca(p,q)) steps from p towards root, followed by d(q)-d(lca(p,q)) steps to q.
3a. If L is odd, then the central node of the path is: up(p,(L-1)/2).
3b. If L is even and d(p)=d(q), then the centers are: { up(p,L/2), up(q,L/2) }.
3c. If L is even and d(p)>d(q), then the centers are: { up(p,L/2), up(p,L/2+1) }.

Function up(x,k) can be computed in O(log n) time after O(n log n) preprocessing; just precompute all up(x,2^i).

[Pavel Nalivaiko]

The choice of the root doesn't matter at all! (My solution always uses node #1 as root.)

Wow.. cool Thank you!