17964번 - Tree Permutations 다국어

Once upon a time, Mr. Cool created a tree (an undirected graph without cycles) of n vertices, by assigning to each vertex i > 1 two numbers: p_i < i — the direct ancestor of vertex i and w_i — the weight of the edge between vertex i and p_i. Vertex 1 is the root, so it does not have any ancestors.

You wanted to know what tree did Mr. Cool build, but Mr. Cool refused to tell this, but he gave you a tip:

He wrote all these numbers in one line. That’s how he got array b of length 2 · n − 2.

b = [p₂, w₂, p₃, w₃, . . . , p_n−1, w_n−1, p_n, w_n]

Then he randomly shuffled it. That’s how he got array a, and Mr. Cool presented you with it.

Since it is impossible to restore the tree knowing only values of array a, you decided to solve a different problem.

Let’s call a tree k-long, if there are exactly k edges on the path between vertex 1 and n.

Let’s call a tree k-perfect, if it is k-long and the sum of the weights of the edges on the path between vertex 1 and vertex n is maximal among all possible k-long trees that Mr. Cool could build.

Your task is to print the sum of the weights of the edges on the path between vertex 1 and vertex n for all possible k-perfect trees or print −1 if a certain k-long tree could not be built by Mr. Cool.

The first line contains one integer n (2 ≤ n ≤ 10⁵) — the number of the vertices in the tree.

The second line contains 2 · n − 2 integers a₁, a₂, . . . , a_2n−2 (1 ≤ a_i ≤ n − 1) — the elements of array a.

In one line, print n − 1 space-separated integers w₁, w₂, w₃, . . . , w_n−1, where w_k — the sum of the weights of the edges on the path between vertex 1 and vertex n in a k-perfect tree. If there is no i-long tree, then wi should be equal to −1.

In the first example, the 1-perfect tree is defined by array [1, 2, 1, 2] (i.e. p₂ = 1, w₂ = 2, p₃ = 1, w₃ = 2). The 2-perfect tree is defined by array [1, 2, 2, 1] (i.e p₂ = 1, w₂ = 2, p₃ = 2, w₃ = 1). Here are illustrations of the 1-perfect tree and the 2-perfect tree respectively (path from vertex 1 to vertex n is drawn with bold lines):

In the second example, there are no k-perfect trees, that can be obtained by permuting array a.

In the third example, only 4-perfect tree and 5-perfect tree can be obtained. These are defined by arrays [1, 4, 2, 4, 3, 4, 4, 4, 4, 5] and [1, 4, 2, 4, 3, 4, 4, 4, 5, 4] respectively. Here are illustrations of them: