Maximizing Path Weight in a Shuffled Tree

One day, Mr. Cool built a tree with n nodes (a connected, acyclic undirected graph). For every node with index i > 1, he assigned two numbers: a parent index p_i (with the restriction \(p_i < i\)) and an edge weight \(w_i\) on the edge between node i and its parent. Node 1 is the root and has no parent.

He then wrote the values \(p_2, w_2, p_3, w_3, \dots, p_n, w_n\) in order into an array \(b\) of length \(2n-2\). After that, he randomly shuffled \(b\) to get an array \(a\) and told you the sequence \(a\). Of course, with just \(a\) you cannot restore the original tree. So you decide to tackle a harder problem.

Define a tree to be \(k\)-long if and only if the unique path from node 1 to node n has exactly \(k\) edges. A tree is called \(k\)-perfect if it is \(k\)-long and, among all \(k\)-long trees, the sum of the weights on the path from node 1 to node n is maximized.

Your task is: given the integer n and the shuffled array a (of length \(2n-2\)), compute for each \(k\) (\(1 \le k \le n-1\)) the maximum possible sum of the edge weights on the path from 1 to n in a \(k\)-perfect tree. If no valid \(k\)-long tree exists (i.e. a valid tree cannot be built that makes the path from 1 to n have exactly \(k\) edges), output -1 for that \(k\>.

Note on constructing a valid tree: A valid tree is one in which for every node i > 1 you assign a parent value from the array such that the condition \(p_i < i\) holds, and each number from a is used exactly once (either as some p_i or as some \(w_i\)). In particular, observe that for node 2, the only valid parent is 1; hence at least one occurrence of 1 must appear in a (and must be used as a parent value rather than as an edge weight).

Hint: You have full freedom to partition the shuffled array \(a\) into two groups of size \(n-1\): one for the parent indices and one for the edge weights. To maximize the sum on the 1-to-n path, you would like to assign the largest possible numbers to the edge weights along that path. However, if there is exactly one occurrence of 1 in \(a\) (which is required for node 2), you must reserve it in the parent group. Based on this observation, an optimal strategy is to choose the partition so that the edge weight group obtains the maximum numbers possible subject to the constraint that the parent group contains at least one 1.

inputFormat

The input consists of two lines:

1. The first line contains an integer n (n ≥ 2), the number of nodes in the tree.
2. The second line contains \(2n-2\) space‐separated integers representing the shuffled array a.

You can assume that all numbers are integers. Note that a valid tree can only exist if at least one 1 appears in a (to serve as the parent of node 2).

outputFormat

Output \(n-1\) space-separated integers. The \(k\)-th integer (for \(1 \le k \le n-1\)) should be the maximum sum of edge weights on the path from node 1 to node n in a \(k\)-perfect tree. If no \(k\)-long tree can be constructed, output -1 for that \(k\>.

sample

3
4 3 2 1

4 7