Automatic Distribution (APCS 2020-01 Expert)
2.0s 256MA packing device is a binary tree rooted at vertex \(1\). Its \(n\) container leaves are numbered \(n\) through \(2n-1\); internal splitters are numbered \(1\) through \(n-1\), each with a left and a right child. Containers initially hold given weights. Send \(m\) items through the device in order. At each splitter, an item enters the child subtree with the smaller current total container weight, choosing the left child on a tie. Add the item weight to the container it reaches before sending the next item. Report each destination container.
Input Format
The first line contains \(n,m\). The second gives initial container weights in increasing container order. The third gives item weights in arrival order. Each of the next \(n-1\) lines contains a splitter index, its left child, and its right child. These lines may appear in any order.
Output Format
Print the destination container indices in arrival order, separated by spaces.
Constraints
\(1\le n\le100000\), \(1\le m\le100\). Initial weights are nonnegative integers and item weights are positive integers. Their combined total is at most \(10^9\). The input describes a valid tree of the stated form.
Sample Input 1
4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7
Sample Output 1
4 6 7 5 5
Sample Input 2
7 2
9 2 1 6 8 7 5
2 3
1 2 5
2 3 7
3 13 10
4 11 9
6 12 8
5 6 4
Sample Output 2
8 7
Source
APCS 2020-01 public archive version: tcirc:d105。
Log in to write and submit code.
Log in