## PIB '20 P6 - Rotational Top Trees

View as PDF

Points: 20 (partial)
Time limit: 1.5s
Memory limit: 256M

Author:
Problem types

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 is 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.

#### 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 dependant on the query form.

There will only be type 1 queries.

#### 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