Static Tree Test


Submit solution


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

Problem types

Given a unweighted tree of \(N\) nodes numbered from \(1\) to \(N\), rooted at Node \(1\), and each node \(u\) has a given initial value \(v_u\), support the following operations:

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

You will be asked to perform these operations a total of \(Q\) times.

Constraints

  • \(1 \leq N, Q \leq 10^5\)
  • \(1 \leq v_u, x, \leq 10^4\)
  • \(1 \leq u, v, \leq N\)

Input Specification

The first line will contain \(N\) and \(Q\).

The second line will contain \(N\) numbers: the \(u\)-th number is \(v_u\).

The next line contains \(N\) numbers: the \(u\)-th number is \(p_u\), the parent of \(u\). Since Node \(1\) is always the root, the first number of input, \(p_1\), is always \(0\), representing no parent.

The next \(Q\) 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

Comments

There are no comments at the moment.