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
Bir Bahadur Khatri