Hard Divide and Conquer > Centroid Decomposition

You are given a **Tree** having **N** nodes . Each node have given value initially. To travel from one node to another node, there is exactly one way . The distance between adjacent node is **One**. **Motku** is the sum of value of nodes on the path from **U to V** . You have to answer **Q** Queries .Queries is described as follows. **.** You will be given a node **U** and value **K**. Can you find the node which is at a distance K (exactly ) from node U? If there are many nodes at distance K from node U then find the minimum **Motku** among of them. Input: ------ Input contains an integer **N (1 ≤ N ≤ 300000)** denoting the number of Nodes of tree.The next line will contain N integers separated by spaces, denoting the value( Val[i] ) of nodes from **1 to N** Such that[ **0<=Val[i]<=1000000.**] The N-1 next line will contain two integers , **a and b** denoting that there is edge between a and b. The next line will contain a number **1<=Q<=100000**. denoting the number of queries. Each query will contain **U and K**. [**1<=U<=N, 0<=K<=300000**]. It is **not guaranteed** that there exist a node at a distance K from U. Output: ------- **For each query** If there don't exits a node at a distance K from U then print **-1**. else you have to print a line containing the **Answer**. **Answer**= The minimum **Motku** value at distance K from node U. Sample Input ------------ 6 5 8 7 3 2 1 1 2 1 3 2 4 3 5 3 6 4 5 2 6 3 4 3 4 2 Sample Output ------------- 10 21 23 16 **Sample Case Description** **First query** ( U=5,K= 2) There are two nodes at distance 2 from node 5. These are Nodes 1 and 6. To reach node 1 Motku value is = 2+7+5=14 To reach node 6 Motku value is = 2+7+1=10 So minimum Motku is **10**

Bir Bahadur Khatri