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
Subtasks
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
Comments