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 –

  1. 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.
  2. 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 Hiearchy

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 ≤ 105)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 ith (1 ≤ i ≤ N) line contains two integers pi and si (0 ≤ pi ≤  N, 1 ≤ si < 500)pi denotes the parent and si denotes the salary of the ith 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: 2018-12-04 01:37:23

Very Nice question.
A problem that teaches you something new is a good problem.
A problem that teaches you many things is.... just awesome.

memetkagan44: 2017-12-08 12:26:43

@blackjack123
I think that this is what they were aiming to say:
update -> increase everybody's salary by min(min(him/her and staff),1000);

rishabhjain996: 2016-09-12 12:11:42

interesting ques :)
several WA's for not using long long -_-
cin /scanf both work :)

Last edit: 2016-09-12 12:16:18
nonushikhar: 2016-09-11 14:36:01

easy one :)

iharsh234: 2016-09-01 20:49:33

One of Best Ques I have done on Spoj.
Thanks:)

sieunhanbom04: 2016-08-23 11:48:46

the most annoying thing in SPOJ problems is that they have many test cases...

blackjack123: 2016-08-20 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: 2016-08-20 09:48:24
sanjog1409: 2016-06-23 15:45:01

Very nice problem :)
Don't forget to use long long

kejriwal: 2016-01-02 10:51:20

new lesson learnt :) !!..thanks for such a nice problem :D

Archit Sharma: 2015-10-01 21:42:29

A lazy implementation on the tree itself (Recursion traverses upwards). Still gives me TLE?


Added by:Faiyaz
Date:2013-12-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64