SALMAN  Salary Management
Salary Management
You are working as a software engineer of Moogle! Now the boss of Moogle wants you to create a program which will efficiently handle some operations. At first, we should tell you about the structure of the employees at Moogle! Each employee has an integer id from 1 to N. Where 1 is the id of the Managing Director of Moogle! , who is the greatest boss of all the employees. Then except the Managing Director, each employee has an immediate boss. No employees have more than one immediate boss. Now your boss wants to have some operation like this –
 He will give you an ID of an employee; you need to find the sum of salary of all the employees under that employee including him/herself.
 He will give you an ID of an employee; you need to increase the salary of all the employees under that employee including him/herself by the minimum of minimum salary of all the employees under that employee including him/her and 1000.
Let’s see the structure, hope you will get a clear idea about the problem.
Employee Hierarchy
Salary Table:
ID 
1 
2 
3 
4 
5 
6 
7 
Salary (BDT) 
500 
300 
200 
100 
10 
200 
100 
Now if your boss wants to do the first operation for Employee ID 2. Then the output will be
300+100+200= 600 BDT
If your boss wants to do the second operation for the Employee ID 1, then the salary table becomes 
ID 
1 
2 
3 
4 
5 
6 
7 
Salary (BDT) 
510 
310 
210 
110 
20 
210 
110 
As minimum salary is 10 for Employee id 5 and which is less than 1000.
Input
Input starts with an integer T (≤ 3), denoting the number of test cases.
The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 10^{5}), q (1 ≤ q ≤ 50000) where N denotes the number of nodes and q denotes the number of queries. The nodes are numbered from 1 to N.
Then there will be N lines. The i^{th} (1 ≤ i ≤ N) line contains two integers p_{i} and s_{i} (0 ≤ p_{i} ≤ N, 1 ≤ s_{i} < 500). p_{i} denotes the parent and s_{i} denotes the salary of the i^{th} employee, respectively. You can assume that the employee id with 1 is the managing director and only its parent is 0.
Each of the next q lines contains a query. Each query contains two integers: c and v (1 ≤ c ≤ 2, 1 ≤ v ≤ N), where c denotes operation type, and v denotes the employee id. If the c = 1, then it means to do the first operation. If c=2, then the second operation.
You can assume that the input builds a valid rooted tree.
Output
For each case, print the case number in a line. Then for each query type 1, print the sum of the salary.
Sample Input 
Output for Sample Input 
1 7 3 0 500 1 300 1 200 1 100 3 10 2 200 2 100 1 2 2 1 1 2 
Case 1: 600 630 
Note
Dataset is huge. Use faster I/O methods.
Problem Setter: Ahmad Faiyaz
Special Thanks: Syed Shahriar Manjur
hide comments
phoemur:
20181204 01:37:23
Very Nice question.


memetkagan44:
20171208 12:26:43
@blackjack123


rishabhjain996:
20160912 12:11:42
interesting ques :)


nonushikhar:
20160911 14:36:01
easy one :) 

iharsh234:
20160901 20:49:33
One of Best Ques I have done on Spoj.


sieunhanbom04:
20160823 11:48:46
the most annoying thing in SPOJ problems is that they have many test cases... 

blackjack123:
20160820 09:21:08
update query is not clear , pls any body explane me what does "under that employee including him/her and 1000." mean. Last edit: 20160820 09:48:24 

sanjog1409:
20160623 15:45:01
Very nice problem :)


kejriwal:
20160102 10:51:20
new lesson learnt :) !!..thanks for such a nice problem :D 

Archit Sharma:
20151001 21:42:29
A lazy implementation on the tree itself (Recursion traverses upwards). Still gives me TLE? 
Added by:  Faiyaz 
Date:  20131224 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 