## Dynamic Tree Test

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.