Dynamic Tree Test

View as PDF

Points: 45
Time limit: 1.4s
Memory limit: 256M

Problem type

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

Input

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

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

Then there are more lines, each containing one number: the initial weight of each vertex.

Then next line contains the root.

Then there are lines:

The first number is .

means subtree modification. is followed by and . This operation sets all vertex weights in the subtree of to .

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 subtree min. is followed by , the root of the queried subtree.

means subtree max. is followed by , the root of the queried subtree.

means increment subtree. is followed by and , the root of the queried subtree and the value to increment by.

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 , the endpoints of the queried path.

means path max. is followed by and , the endpoints of the queried path.

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 path sum. is followed by and , and asks for the sum of the weights on the path from to .

means subtree sum. is followed by , and asks for the sum of the weights in the subtree root at .

Output

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

Sample Input 1

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

Sample Output 1

9
1
1

Sample Input 2

10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5

Sample Output 2

173
860
103
791
608
1557

Constraints

All intermediate values can be stored in a C++ int.