PIB '20 P6 - Rotational Top Trees

View as PDF

Submit solution

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

Author:
Problem types

You are given a one-indexed tree of N nodes and N1 edges. Each node has a weight wi.

Your friend asks you Q questions with regards to the structure of the tree of the following forms:

  • 1 r k If the root of the tree is node r, what is the heaviness of the kth 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 r, what is the heaviness of the kth 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 1r,kN. Recall that there are always exactly N subtrees in a tree. The kth 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 N,Q (1N,Q105).

The next line will contain N integers, wi (|wi|109).

The next N1 lines will each contain two integers, ui,vi (1ui,viN), indicating that nodes ui and vi are connected by an edge. It is guaranteed that the entire tree is connected.

The next Q lines will each contain a question as defined above.

Output Specification

For each question, output the heaviness of the kth heaviest subtree if the root of the tree is node r, where the definition of heaviness is dependent on the query form.

Subtasks

Subtask 1 [14%]

N2000

Subtask 2 [39%]

There will only be type 1 queries.

Subtask 3 [47%]

No additional constraints.

Sample Input for Subtask 1

Copy
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

Copy
1
4
0
-2
4

Sample Input for Subtask 2

Copy
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

Copy
-1
5
2
-3

Sample Input for Subtask 3

Copy
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

Copy
17
11
-9
-2
1
17
0
0
3
13

Comments

There are no comments at the moment.