DCP-141: Motku Back to All Problems

Hard Graph Theory > Breadth First Search/Depth First Search

A Pharmaceutical company has n employees numbered fron **1 to N**. Each employee either has no immediate manager or exactly one immediate manager. Employee **1** has no immediate manager so He is **BOSS** . Each employees are ranked by seniority. Boss has a maximum **rank**. If A is immediate manager of B then A 's rank is more than B. Different employee can have a same immediate manager. Each employee have their weight in **kg**. **Motku** is a medicine which increases a person's weight in per use. If a person weight is **W** Kg, if He/She uses Motku with power level **K** then new weight will be **W*K** Kg. Every employee are angry with their respective managers. So if a employee got this medicine, then He/She uses it and passes to manager. ( He/She will also uses because they don't know the effect before use ). After one use the power level will decrease by **one** .Medicine will work until Power **level>=1**. CEO of company wants to know the summation of weight of each employee who will use the medicine If CEO gives the medicine to Employee number **U** and power level of medicine is **K**. Boss cannot pass the medicine to no-one. Input: ------ Input contains an integer **N (1 ≤ N ≤ 100000)** denoting the number of employees. The **N-1** next line will contain two integers , **a and b** denoting that a is manager of b.The next line will contain N integers separated by spaces, denoting the weight of employee from 1 to N. **0<=W[i]<=100000**. The next line will contain a number **Q<=100000.** denoting the number of queries. Each query will contain U and K. **[1<=U<=N, 1<=K<=100000]** Output: ------- For each query you have to print a line containing the **Answer**. Sample Input ------------ 5 1 2 1 3 2 4 2 5 5 7 2 3 4 2 4 2 5 5 Sample Output ------------- 13 63 Sample Case Description -------- **First query** When medicine is with employee 4 with power 2. He/She uses it and weight becomes 3*2=6. Then passes to employee 2. employee 2 uses it with power level 1 then his/her weight becomes 7*1=7. After this power level of medicine becomes zero ( useless ). So total weight of person who uses medicine is 6+7=13

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# 5.00
Go 5.00
Java 5.00
JavaScript 5.00
Objective-C 5.00
Perl 5.00
PHP 5.00
Python 5.00
Python3 5.00
Ruby 5.00
VB.Net 5.00

Problem Stats




# User Language Timing
01 Robbinb1993 Cpp14 0.16s
02 seyedssz Cpp14 0.23s
03 Double_O Cpp14 0.24s
04 Morass Cpp14 0.27s
05 Knight_of_Thirteen Cpp14 0.43s
06 raihatneloy Cpp14 0.71s
07 khatribiru Cpp14 0.80s
08 moinul_shaon Cpp14 1.08s
09 INUA Cpp14 1.12s
10 sahedsohel Cpp14 1.25s

Your feedback is our precious!

Or call +88 02 9853138 for support