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 N-1 edges. Each node has a weight w_i.

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 k^\text{th} 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 k^\text{th} 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 1 \le r, k \le N. Recall that there is always exactly N subtrees in a tree. The k^\text{th} 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 (1 \le N, Q \le 10^5).

The next line will contain N integers, w_i (|w_i| \le 10^9).

The next N-1 lines will each contain two integers, u_i, v_i (1 \le u_i, v_i \le N), indicating that nodes u_i and v_i 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 k^\text{th} heaviest subtree if the root of the tree is node r, where the definition of heaviness is dependant on the query form.

Subtasks

Subtask 1 [14%]

N \le 2000

Subtask 2 [39%]

There will only be type 1 queries.

Subtask 3 [47%]

No further 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 Sample 3

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

Comments

There are no comments at the moment.