Problem : Given a tree, you have to answer the question of the format “r u v” which means which is the LCA of u and v if the root of the tree is at r.
Explanation
At first, let’s consider some partial solutions.
How to get 20 points
For this sub-task you an find the LCA in any way you want as long as the complexity is not slower than O(N). For example, by DFS from the root, you can number the vertices so that given two arbitrary vertices, you can check whether they are ancestor and descendant(for this, you can store T_in and T_out for each node. T_in is the time when the DFS for that node was begun. T_out is the time when the DFS was over).
How to get 60 points
Here there are not more than 10 different roots, but the queries are quite high, so you should know the fast way to find LCA. More specifically O(Nlog(N)) is enough. Notice that there will be no more than 10 different roots so your complexity will be O(10 × Nlog(N)).
How to get 100 points
There are two interesting observations that you can make:
Given the query “r u v” what can be the answer? The possible answers are r, u, v, LCA(r, u), LCA(r, v), LCA(u, v) where LCA(x, y) is LCA of x and y when the tree is rooted at 1.
The LCA of u and v when the root is at r is the vertex x such that the sum of shortest path from x to u, x to v and x to r is smallest.
With this two observations you need to implement two function: finding LCA and distance of the two vertices in the tree. Proof for these two observation is not hard but too long to be mentioned here. It is left as an exercise for you.
Let a=LCA(u,v),b=LCA(root,u) and c=LCA(root,v)
and the answer for the query is the one value that is different from other two if all of them are not equal
i.e
if(a==b)return c;
else if(b==c)return a;
else if(c==a)return b;
else throw an error ; // condition no possible
What is wrong with my solution:
What I am doing is :
If r is not in subtree of orig_lca then origlca is the answer
else {
if(lca(u,r)==origlca and lca(v,r)==origlca){
then answer = origlca
}
if(lca(u,r)==origlca){
then answer = lca(v,r);
}
if(none of above){
then answer = lca(u,r);
}
}
Infact, the only possible answers are LCA(r, u), LCA(r, v), LCA(u, v). I proved it by drawing the diagrams corresponding to all possible scenarios for the arrangements of the 3 nodes and the node no. 1.
Those who are looking for an explanation of the StackOverflow answer
Here is it:
Lets say we have calculated of LCA of every node with respect to any arbitrary root R
So the query is LCA of U and V when tree is rooted at W.
LCA(U,V) will lie on the shortest path from U to V ,every node which lie on the path from U to V is the potential candidate for LCA depending upon the Root.
So, According to 1st point - 1. The LCA of u and v when the root is at r is the vertex x such that the sum of shortest path from x to u, x to v and x to r is smallest.
Which means all the nodes which lie on the shortest path from U to V will also have to be shortest distance from the Root node.
Let when tree is rooted at R
LCA(U,V)=p
LCA(U,W)=q
LCA(V,W)=r
Node lie on shortest path from U to V and p is shortest distance from Root R.
Node q is shortest distance from Root U and W.
Node r is shortest distance from Root V and W.
Since we have to find LCS with respect to W and LCS must lie on the shortest path from U to V ,which is shortest distance to W also,So q and r node are the possible candidates for LCS w.r.t W.
If W is closer to node U than q will be the answer =>(p==r)
if W is closer to node V than r will be the answer =>(p==q)
if W is at equal distance from U and V than p will be the answer=>(p==q==r)