DCP-176: Motku2 Back to All Problems

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**

Problem Setter:

Bir Bahadur Khatri

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 4.00
Go 4.00
Java 4.00
JavaScript 4.00
Objective-C 4.00
Perl 4.00
PHP 4.00
Python 4.00
Python3 4.00
Ruby 4.00
VB.Net 4.00

Problem Stats




# User Language Timing
01 Morass Cpp14 1.15s
02 khatribiru Cpp 1.57s
03 rubabredwan Cpp14 1.72s
04 win11905 Cpp14 1.74s
05 Robbinb1993 Cpp14 1.88s
06 seyedssz Cpp14 1.95s
07 SpeedOfMagic Cpp14 1.96s
08 luciocf Cpp14 1.96s
09 tariqiitju Cpp14 1.97s
10 kzvd4729 Cpp14 1.99s

Your feedback is our precious!

Or call +88 02 9853138 for support