LCA (Least Common Ancestor) Problem
Moderator: Board moderators

 New poster
 Posts: 15
 Joined: Sun Mar 07, 2004 7:47 pm
 Location: Moscow, Russia
LCA (Least Common Ancestor) Problem
Can anyone recommend me some problem in UVA's problemset to test my solution to the LCA problem?

 New poster
 Posts: 15
 Joined: Sun Mar 07, 2004 7:47 pm
 Location: Moscow, Russia
Thank you, but..mf wrote:10938 "Flea circus" can be solved with LCA.
.. 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...
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,k1) for k>0. (i.e. up(x,k) is the kth 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,(L1)/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).
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,k1) for k>0. (i.e. up(x,k) is the kth 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,(L1)/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).

 New poster
 Posts: 15
 Joined: Sun Mar 07, 2004 7:47 pm
 Location: Moscow, Russia