## Static Tree Test

View as PDF

Points: 20
Time limit: 2.0s
Memory limit: 256M

Problem types

Given a unweighted tree rooted at of nodes numbered from to , rooted at Node , and each node has a given initial value , support the following operations:

• 1 u x: Increment the subtree of node by the value
• 2 u v x: Increment all nodes along the path from to by the value
• 3 u: Output the maximum value of all nodes in the subtree of
• 4 u v: Output the maximum value of all nodes along the path from to

You will be asked to perform these operations a total of times.

#### Input Specification

The first line will contain and .

The second line will contain numbers: the -th number is .

The next line contains numbers: the -th number is , the parent of . Since Node is always the root, the first number of input, , is always , representing no parent.

The next lines contain operations as described above.

#### Sample Input 1

5 4
1 2 3 4 5
0 1 1 2 2
1 1 10
2 4 5 10
3 3
4 1 5

#### Sample Output 1

13
25

#### Sample Input 2

10 10
9384 887 2778 6916 7794 8336 5387 493 6650 1422
0 1 2 3 4 4 5 4 3 8
1 9 5212
4 3 10
3 3
4 6 8
2 9 3 9803
2 7 4 8168
4 10 3
2 5 10 4422
2 6 5 5199
3 4

#### Sample Output 2

6916
11862
8336
15084
25583