Dynamic Tree Test (Easy)

View as PDF

Points: 25 (partial)
Time limit: 1.0s
PyPy 2 15.0s
PyPy 3 15.0s
Memory limit: 128M
PyPy 2 256M
PyPy 3 256M

Authors:
Problem type

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

Input Specification

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

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

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

Then next line contains the root.

Then there are lines:

The first number is .

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

means path modification. is followed by integers . This operation sets as the vertex weight of all vertices on the path from to .

means path increment. is followed by . This operation increments all vertex weights on the path from to by .

means path min. is followed by and , and asks for the min of the weights on the path from to .

means path max. is followed by and , and asks for the max of the weights on the path from to .

means path sum. is followed by and , and asks for the sum of the weights on the path from to .

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

means lowest common ancestor (LCA). is followed by and . This operation queries the LCA of and .

Output Specification

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

Constraints

For 20% of the points, .

For 50% of the points, .

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