Given an undirected rooted tree at node 1, consisting of N nodes. Find the kth ancestor of a given node. There will be Q queries.
Input:
First line contains N, the number of nodes in the tree. Next N - 1 lines contains two integers u and v, there is an edge between u and v. Next line contains Q, the number of queries. Each of the next Q lines contains a node p and and integer k.
Output:
Print on a single line the answer of query as described.
Constraints:
\( 1 \leq N,k,p \leq 10^5 \)
\( 1 \leq Q \leq 10^5 \)
\( 1 \leq u , v \leq 10^5 \)
Update: In case No ancestor exists, output root node i.e, 1.
Problem Setter - Saurabh
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor