Weights Assignment For Tree Edges solution codeforces

Weights Assignment For Tree Edges solution codeforces

You are given a rooted tree consisting of nn vertices. Vertices are numbered from 11 to nn. 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 bb containing nn numbers: bibi is an ancestor of the vertex with the number ii. The ancestor of a vertex uu is a vertex that is the next vertex on a simple path from uu 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. Weights Assignment For Tree Edges solution codeforces

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

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

An example of a rooted tree for n=5n=5, the root of the tree is a vertex number 33.
You are given an array pp — 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 pp.

In other words, for a given permutation of vertices pp, it is necessary to choose such edge weights so that the condition dist[pi]<dist[pi+1]dist[pi]<dist[pi+1] is true for each ii from 11 to n1n−1dist[u]dist[u] is a sum of the weights of the edges on the path from the root to uu. In particular, dist[u]=0dist[u]=0 if the vertex uu is the root of the tree. Weights Assignment For Tree Edges solution codeforces

For example, assume that p=[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.

The array of distances from the root looks like: dist=[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 pp.

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.

Weights Assignment For Tree Edges solution codeforces Input

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

Each test case consists of three lines.

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

The second line contains nn integers b1,b2,,bnb1,b2,…,bn (1bin1≤bi≤n). It is guaranteed that the bb array encodes some rooted tree.

The third line contains the given permutation ppnn of different integers p1,p2,,pnp1,p2,…,pn (1pin1≤pi≤n).

It is guaranteed that the sum of the values nn 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 nn integers w1,w2,,wnw1,w2,…,wn, where wiwi is the weight of the edge that leads from bibi to ii. For the root there is no such edge, so use the value wi=0wi=0. For all other vertices, the values of wiwi must satisfy the inequality 1wi1091≤wi≤109. There can be equal numbers among wiwi 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.

Weights Assignment For Tree Edges solution codeforces Example


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


1 10 0 102 100
0 3 100 1 1 2 4
6 5 10 0 2 3

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.

Leave a Comment