Dynamic Tree Test (Easy)

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 3.0s
Memory limit: 128M
Authors:

Problem type

Today, we'll be practicing modifications on a tree!

Input Specification

The first line contains two integers, N and M, denoting that there are N vertices and M queries.

Then there are N integers on the next line, each containing one number: the initial weight of each vertex.

Then there are N-1 lines, each line containing two integers x and y, denoting that there is an edge between x and y in the tree.

Then next line contains the root.

Then there are M lines:

The first number is K.

K=0 means change root. The line contains one additional integer x, representing the new root of the tree.

K=1 means path modification. K is followed by integers x,y,z. This operation sets z as the vertex weight of all vertices on the path from x to y.

K=2 means path increment. K is followed by x,y,z. This operation increments all vertex weights on the path from x to y by z.

K=3 means path min. K is followed by x and y, and asks for the min of the weights on the path from x to y.

K=4 means path max. K is followed by x and y, and asks for the max of the weights on the path from x to y.

K=5 means path sum. K is followed by x and y, and asks for the sum of the weights on the path from x to y.

K=6 means change parent. K is followed by x and y. The operations changes the parent of x to y. If y is in the subtree of this operation, do nothing.

K=7 means lowest common ancestor (LCA). K is followed by x and y. This operation queries the LCA of x and y.

Output Specification

Print an answer for each query. All answers go on their own lines.

Constraints

1 \le N,M \le 10^5, 1 \le x,y \le N

Subtasks

For 20% of the points, K \ne 0, K \ne 1, K \ne 2, K \ne 6.

For 50% of the points, K \ne 0, K \ne 6.

All intermediate values can be stored in a signed 32-bit integer.

Sample Input 1

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

Sample Output 1

1
3
6
17

Sample Input 2

9 13
100 2 1 3 6 5 4 7 8
1 2
1 3
2 4
2 7
3 6
3 8
3 5
5 9
1
1 1 2 101
2 2 2 101
3 8 5
7 9 4
7 3 8
0 4
7 4 7
0 5
7 1 5
6 9 8
5 6 9
3 8 5
4 4 6

Sample Output 2

1
1
3
4
5
21
1
202

Comments