ROOTLESS - Editorial

editorial
, , , ,
1

Problem Link:
Practice
Contest

Author: murugappan_s
Testers: sdssudhu,msv99999
Editorialist: murugappan_s

DIFFICULTY: Medium-Hard

PREREQUISITES: LCA, DFS

PROBLEM:

We have a tree with N nodes, with each node numbered uniquely with 1…N.

Movement from a particular node to its parent(if exists) is the only allowed move and it costs 1 rupee. That is from any node U we can go to parent(U) in 1 rupee, parent(parent(U)) in 2 rupees, parent(parent(parent(U))) in 3 rupees etc.

We have Q queries of the form r, u, v and each query is interpreted as follows:

  • The tree is rooted at r
  • One person is standing at u and another one is standing at v* .
  • Both of them want to meet at a common location with each one spending as minimum as possible.
  • The answer to the query is x y, where x is the minimum cost for the person standing initially at u and y is the minimum cost for the person standing initially at v to meet in a common location.

CONSTRAINTS:

  • 1≤N,Q≤10^5
  • 1≤Nodenumber≤N
  • 1≤r,u,v≤N

SOLUTION:

We can easily observe that for query r,u,v , the target node is LCA(u,v)(lca:Least Common Ancestor) with tree rooted at r, because LCA(u,v) would be the first node if only movement to parent is possible.

So the major part of the solution is to find the LCA(u,v) with the root r. If the root was fixed then the problem would have been simple, but the root is not fixed here.

So how do we find the LCA(u,v) for a given root r. Let us consider all possible cases.
Consider the tree to be rooted at 1 and let LCA(u,v) with root=1 be p.

Case 1: r is outside the subtree of p.
In this case the NewLca is still p. This can be tested by finding the LCA(p,r), if it is not equal to p then r is outside the subtree of p.

Case 2: r is in the subtree of one of the nodes in the path between [u,p).
In this case the NewLca is LCA(u,r). This can be tested by finding the LCA(u,r), if it is not equal to p then this case satisfied.

Case 3: r is in the subtree of one of the nodes in the path between [v,p).
In this case the NewLca is LCA(v,r). This can be tested by finding the LCA(v,r), if it is not equal to p then this case satisfied.

Case 4: r is in the subtree of p but not in the subtree of one of the nodes in the path [u,p) or [v,p).
In this case the NewLca is still p. This can be tested by testing the first 3 cases and ensuring that none of them is satisfied.

Now we have the NewLca, we have to find the distance of (u,NewLca) and (v,NewLca). Distance between any two nodes (x,y) is equal to depth[x]+depth[y]-2*depth[LCA(x,y)].

Note: In all the cases we used LCA precomputation with root as 1.

3 Likes