[Solution] Weights Assignment For Tree Edges solution codeforces

Weights Assignment For Tree Edges solution codeforces

You are given a rooted tree consisting of 𝑛n vertices. Vertices are numbered from 11 to 𝑛n. Any vertex can be the root of a tree.

tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root.

The tree is specified by an array of ancestors 𝑏b containing 𝑛n numbers: 𝑏𝑖bi is an ancestor of the vertex with the number 𝑖i. The ancestor of a vertex 𝑢u is a vertex that is the next vertex on a simple path from 𝑢u to the root. For example, on the simple path from 55 to 33 (the root), the next vertex would be 11, so the ancestor of 55 is 11.

The root has no ancestor, so for it, the value of 𝑏𝑖bi is 𝑖i (the root is the only vertex for which 𝑏𝑖=𝑖bi=i).

For example, if 𝑛=5n=5 and 𝑏=[3,1,3,3,1]b=[3,1,3,3,1], then the tree looks like this.

An example of a rooted tree for 𝑛=5n=5, the root of the tree is a vertex number 33.
You are given an array 𝑝p — a permutation of the vertices of the tree. If it is possible, assign any positive integer weights on the edges, so that the vertices sorted by distance from the root would form the given permutation 𝑝p.

Also read: ATM and Students solution codeforces

In other words, for a given permutation of vertices 𝑝p, it is necessary to choose such edge weights so that the condition 𝑑𝑖𝑠𝑡[𝑝𝑖]<𝑑𝑖𝑠𝑡[𝑝𝑖+1]dist[pi]<dist[pi+1] is true for each 𝑖i from 11 to 𝑛1n−1𝑑𝑖𝑠𝑡[𝑢]dist[u] is a sum of the weights of the edges on the path from the root to 𝑢u. In particular, 𝑑𝑖𝑠𝑡[𝑢]=0dist[u]=0 if the vertex 𝑢u is the root of the tree.

For example, assume that 𝑝=[3,1,2,5,4]p=[3,1,2,5,4]. In this case, the following edge weights satisfy this permutation:

  • the edge (3,43,4) has a weight of 102102;
  • the edge (3,13,1) has weight of 11;
  • the edge (1,21,2) has a weight of 1010;
  • the edge (1,51,5) has a weight of 100100.

Weights Assignment For Tree Edges solution codeforces

The array of distances from the root looks like: 𝑑𝑖𝑠𝑡=[1,11,0,102,101]dist=[1,11,0,102,101]. The vertices sorted by increasing the distance from the root form the given permutation 𝑝p.

Print the required edge weights or determine that there is no suitable way to assign weights. If there are several solutions, then print any of them.

Input Weights Assignment For Tree Edges solution codeforces

The first line of input data contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of input data sets in the test.

Each test case consists of three lines.

Also read: Make Even solution codeforces

The first of them contains an integer 𝑛n (1𝑛21051≤n≤2⋅105). It is the number of vertices in the tree.

The second line contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖𝑛1≤bi≤n). It is guaranteed that the 𝑏b array encodes some rooted tree.

The third line contains the given permutation 𝑝p𝑛n of different integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n).

It is guaranteed that the sum of the values 𝑛n over all test cases in the test does not exceed 21052⋅105.

Output Weights Assignment For Tree Edges solution codeforces

For each set of input data print the answer on a separate line.

If the solution exists, print an array of 𝑛n integers 𝑤1,𝑤2,,𝑤𝑛w1,w2,…,wn, where 𝑤𝑖wi is the weight of the edge that leads from 𝑏𝑖bi to 𝑖i. For the root there is no such edge, so use the value 𝑤𝑖=0wi=0. For all other vertices, the values of 𝑤𝑖wi must satisfy the inequality 1𝑤𝑖1091≤wi≤109. There can be equal numbers among 𝑤𝑖wi values, but all sums of weights of edges from the root to vertices must be different and satisfy the given permutation.

If there are several solutions, output any of them.

If no solution exists, output -1.

Example Weights Assignment For Tree Edges solution codeforces

input

Copy
4
5
3 1 3 3 1
3 1 2 5 4
3
1 1 2
3 1 2
7
1 1 2 3 4 5 6
1 2 3 4 5 6 7
6
4 4 4 4 1 1
4 2 1 5 6 3

output

Copy
1 10 0 102 100
-1
0 3 100 1 1 2 4
6 5 10 0 2 3
Note Weights Assignment For Tree Edges solution codeforces

The first set of input data of the example is analyzed in the main part of the statement.

In the second set of input data of the example, it is impossible to assign the positive weights to obtain a given permutation of vertices.

Weights Assignment For Tree Edges solution codeforcesMaximum Number of Tasks You Can Assign solution leetcodeMaximum Number of Tasks You Can Assign solution leetcodeMaximum Number of Tasks You Can Assign solution leetcode

Leave a Comment

Your email address will not be published. Required fields are marked *