DMOPC '19 Contest 7 P3 - Tree Pruning

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Bob's favourite tree consists of N nodes connected by N-1 branches. Each node has a certain weight w_i and the weight of a tree is the sum of the weights of its individual nodes. Bob is trying to enter his tree in a competition, but there is a weight limit of K. Namely, only trees with weights that fall within the range [K,2K] can be entered into the competition. Bob is willing to prune some nodes off his tree such that he is left with a tree which can be entered into the competition. Note that the tree Bob enters into the competition must be connected. Help him find any such tree or determine that no such tree exists.

Input Specification

The first line contains two space-separated integers, N K.
The second line contains N space-separated integers, w_1, w_2, \ldots, w_N.
The next N-1 lines contain two space-separated integers, x_i y_i, denoting a branch connecting nodes x_i and y_i.

Output Specification

If no solution exists, output -1.
Otherwise, output M, the number of nodes in the tree Bob can enter into the competition, followed by the M nodes of the tree on the second line. If there are multiple solutions, output any one of them.

You will receive a Presentation Error verdict if any of the following are true:

  • You do not output enough.
  • You output an invalid value of M (M < 1 or M > N).
  • You do not output the right number of unique nodes (i.e. not equal to M).
  • You do not output a valid node (i.e. you print an index less than 1 or greater than N)

You will receive a Wrong Answer verdict if the weight of your tree does not satisfy the constraints OR if your tree is not connected.


In all subtasks,
1 \le N \le 1\,000\,000
1 \le w_i, K \le 10^{12}

Subtask 1 [10%]

1 \le N \le 20

Subtask 2 [25%]

1 \le N \le 2\,000
1 \le w_i, K \le 2\,000

Subtask 3 [65%]

No additional constraints.

Sample Input

5 9
3 6 2 3 8
1 2
2 3
3 4
4 5

Sample Output

2 3 4

Explanation of Sample Output

Initially, the tree has a weight of 22. Bob can prune off nodes 1 and 5 (with weights of 3 and 8 respectively) to obtain a final tree of weight 11.

Alternatively, another acceptable answer would be:

2 4 1 3


There are no comments at the moment.