Problem:


				Max Score: 1450 Points 

Problem Statement

					There are N workers in Atcoder company. Each worker is numbered 0 through N - 1, and the boss for worker i is p_i like a tree structure and the salary is currently a_i. (p_i < i, especially p_0 = -1 because worker 0 is a president) 

					In atcoder, the boss of boss of boss of ... (repeated k times) worker i called "k-th upper boss", and "k-th lower subordinate" called for vice versa. 

					You have to process Q queries for Atcoder: 

Query 1: You are given v_i, d_i, x_i. Increase the salary of worker v_i, and all j-th (1 ≤ j ≤ d_i) lower subordinates by x_i.

Query 2: You are given v_i, d_i. Calculate the sum of salary of worker v_i and all j-th (1 ≤ j ≤ d_i) lower subordinates.

Query 3: You are given pr_i, ar_i. Now Atcoder has a new worker c! (c is the current number of workers) The boss is pr_i, and the first salary is ar_i.

					Process all queries!!! 

Input Format

						Let the i-th query query_i, the input format is following:

N Q
p_0 a_0
p_1 a_1
 :   :
p_{N - 1} a_{N - 1}
query_0
query_1
 :   :
query_{Q - 1}

						THe format of query_i is one of the three format:

1 v_i d_i x_i

2 v_i d_i

3 pr_i ar_i

Output Format

						Print the result in one line for each query 2.

Constraints

N ≤ 400000

Q ≤ 50000

p_i < i for all valid i.

In each question 1 or 2, worker v_i exists.

d_i ≤ 400000

0 ≤ a_i, x_i ≤ 1000

Scoring

						Subtask 1 [170 points] 

N, Q ≤ 5000

						Subtask 2 [310 points] 

p_i + 1 = i for all valid i.

						Subtask 3 [380 points] 

There are no query 3.

						Subtask 4 [590 points] 

There are no additional constraints.

Sample Input 1

6 7
-1 6
0 5
0 4
2 3
2 2
1 1
2 0 1
1 0 2 1
2 2 1
3 3 3
2 0 3
3 3 4
2 1 1

Sample Output 1

15
12
30
8

Sample Input 2

7 9
-1 1
0 5
0 7
0 8
1 3
4 1
5 1
2 1 1
2 1 2
1 1 2 3
1 4 1 1
2 3 1
2 0 2
3 6 1
3 7 11
2 0 15

Sample Output 2

8
9
8
31
49



Sample input:
6 7
-1 6
0 5
0 4
2 3
2 2
1 1
2 0 1
1 0 2 1
2 2 1
3 3 3
2 0 3
3 3 4
2 1 1


Sample output:
15
12
30
8

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,raw_input().split())
salary = [0] * N
buka = {-1 : []}
for n in range(N):
	p,a = map(int,raw_input().split())
	salary[n] = a
	buka[n] = []
	buka[p].append(n)
for q in range(Q):
	line = list(map(int,raw_input().split()))
	if line[0] == 1:
		v,d,x = line[1:]
		uplist = [v]
		for i in range(d + 1):
			u2 = []
			for j in uplist:
				salary[j] += x
				u2 = u2 + buka[j]
			uplist = u2[:]
	elif line[0] == 2:
		v,d = line[1:]
		ans = 0
		salist = [v]
		for i in range(d + 1):
			s2 = []
			for j in salist:
				ans = ans + salary[j]
				s2 = s2 + buka[j]
			salist = s2[:]
		print ans
	elif line[0] == 3:
		n = n + 1
		p,r = line[1:]
		buka[n] =[]
		buka[p].append(n)
		salary.append(r)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,raw_input().split())
salary = [0] * N
buka = {-1 : []}
for n in range(N):
	p,a = map(int,raw_input().split())
	salary[n] = a
	buka[n] = []
	buka[p].append(n)
for q in range(Q):
	line = list(map(int,raw_input().split()))
	if line[0] == 1:
		v,d,x = line[1:]
		uplist = [v]
		for i in range(d + 1):
			u2 = []
			for j in uplist:
				salary[j] += x
				u2 = u2 + buka[j]
			uplist = u2[:]
	elif line[0] == 2:
		v,d = line[1:]
		ans = 0
		salist = [v]
		for i in range(d + 1):
			s2 = []
			for j in salist:
				ans = ans + salary[j]
				s2 = s2 + buka[j]
			salist = s2[:]
		print ans
	elif line[0] == 3:
		n = n + 1
		p,r = line[1:]
		buka[n] =[]
		buka[p].append(n)
		salary.append(r)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
salary = [0] * N
buka = {-1 : []}
for n in range(N):
	p,a = map(int,input().split())
	salary[n] = a
	buka[n] = []
	buka[p].append(n)
for q in range(Q):
	line = list(map(int,input().split()))
	if line[0] == 1:
		v,d,x = line[1:]
		uplist = [v]
		for i in range(d + 1):
			u2 = []
			for j in uplist:
				salary[j] += x
				u2 = u2 + buka[j]
			uplist = u2[:]
	elif line[0] == 2:
		v,d = line[1:]
		ans = 0
		salist = [v]
		for i in range(d + 1):
			s2 = []
			for j in salist:
				ans = ans + salary[j]
				s2 = s2 + buka[j]
			salist = s2[:]
		print(ans)
	elif line[0] == 3:
		n = n + 1
		p,r = line[1:]
		buka[n] =[]
		buka[p].append(n)
		salary.append(r)