Asked in OA

Revision en1, by Kvschauhan, 2022-07-03 21:07:43

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]

Tags graph, oncampus, codenation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Kvschauhan 2022-07-03 21:07:43 760 Initial revision (published)