Kvschauhan's blog

By Kvschauhan, history, 6 weeks ago, In English

Given a tree with A nodes given in form of 2D array B, where each row consists of 2 integers denoting the presence of an edge between the two integers. Also given another 2D array C of Q queries, each row consists of 3 elements — U, V, and W. Find out the closest node to W on the path from U to V(Path means a subtree in the form of the line containing U, and V as endpoints ). Process each query and return the answer to each query.

Constraint:- 2<=A<=100000 1<=Q<=100000 1<=B[i][0],B[i][1]<=N, B[i][0]!=B[i][1] |B|=A-1 1<=U,V,W<=N(U!=V)

Input 1:- A=6 B=[[1,2],[1,3],[1,4],[3,5],[3,6]] c=[[2,5,6],[5,2,6]]

OUTPUT1:- [3,3]

Input 2:- A=6 B=[[1,2],[1,3],[1,4],[3,5],[3,6]] c=[[2,5,1],[2,5,4]]

OUTPUT2:- [1,1]

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Help!

»
6 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Let's rooted the tree at node 1.

Then calculate the following:-

LCA of U and W :-> x
LCA of V and W :-> y
LCA of U and V :-> z

(LCA is Lowest common ancestor.)

Now there will be 2 cases:-

case1:- x=y. In this case z will be our answer.

case2:- x!=y. In this case if x!=z then answer will be x else answer will be y.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Which company OA is it? oncampus or offcampus?

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice problem, but a bit standard if you know about LCA.
ROHIT_JAIN explained it really well, and here is my solution for the same: https://ideone.com/r4bB3U

Spoiler
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks man!! Could you please provide link of any resource for this algorithm.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I can think of 3 cases here :-

  1. If both U and V are in subtree of W : LCA(U,V)
  2. If either U or V is in subtree of W and other is not : W
  3. If neither U nor V is in subtree of W : Do Binary Lifting on W till either U or V comes in subtree of W, whenever it gets first, that node will be the answer.

To find out whether a node X is in the subtree of node Y or not in constant time, you can use Euler Tour, or If you are okay with O(Logn), then you can apply binary lifting on X till it reaches the depth of node Y.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In case 3 when u or v is in subtree of lifted W. Then we have to find the answer by solving with logic of case 1 or case 2, right?

    Obviously, lifted W is not always going to be on the u-v path.

    Example
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice question