You are given a one-indexed tree of nodes and edges. Each node has a weight .
Your friend asks you questions with regards to the structure of the tree of the following forms:
1 r k
If the root of the tree is node , what is the heaviness of the heaviest subtree in the tree, where the heaviness of a subtree is the sum of all the weights in that subtree?2 r k
If the root of the tree is node , what is the heaviness of the heaviest subtree in the tree, where the heaviness of a subtree is the maximum of all the weights in that subtree?
It is guaranteed that . Recall that there are always exactly subtrees in a tree. The heaviest subtree is out of all the subtrees, not just ones rooted at the children of the root.
Can you answer these questions for your friend?
Input Specification
The first line will contain two integers .
The next line will contain integers, .
The next lines will each contain two integers, , indicating that nodes and are connected by an edge. It is guaranteed that the entire tree is connected.
The next lines will each contain a question as defined above.
Output Specification
For each question, output the heaviness of the heaviest subtree if the root of the tree is node , where the definition of heaviness is dependent on the query form.
Subtasks
Subtask 1 [14%]
Subtask 2 [39%]
There will only be type 1
queries.
Subtask 3 [47%]
No additional constraints.
Sample Input for Subtask 1
7 5
5 3 -2 4 -1 0 -2
1 2
1 3
2 7
3 4
3 5
5 6
1 1 3
2 1 3
1 4 5
2 5 7
2 7 4
Sample Output for Subtask 1
1
4
0
-2
4
Sample Input for Subtask 2
6 4
-2 -1 5 -3 2 4
1 2
1 3
3 4
4 5
4 6
1 4 5
1 4 1
1 6 2
1 6 6
Sample Output for Subtask 2
-1
5
2
-3
Sample Input for Subtask 3
20 10
13 17 -7 -14 -5 11 -10 3 -4 8 -17 3 5 5 1 6 5 -9 0 -19
2 1
3 2
4 3
5 3
6 2
7 2
8 7
9 6
10 2
11 1
12 2
13 4
14 6
15 1
16 13
17 8
18 11
19 13
20 10
2 13 3
2 13 6
2 1 18
1 16 9
1 11 10
2 1 2
2 6 15
2 12 15
1 5 8
2 4 4
Sample Output for Subtask 3
17
11
-9
-2
1
17
0
0
3
13
Comments