I thought of an ad-hoc solution. Try to find a solution such that the first element on the permutation has dist 0 from the root, the second dist 1 from the root, the third dist 2, and so on.

Giving an example (same from the problem text)

5 3 1 3 3 1 3 1 2 5 4

You want the dist array to be [ 0, 1, 2, 3, 4 ] so dist(root, 3) = 0, dist(root, 1) == 1, dist(root, 2) == 2, dist(root, 5) == 3, dist(root, 4) == 4.

So, you have to notice one thing: it's impossible to have a node a such that dist(root, a) <= dist(root, father_of_a) since all the edges must have positive value. You need to check this before by seeing if the position of 'a' in the permutation is before the position of 'father_of_a' in the permutation, but there's also another way of doing it that I'm going to talk about below.

So now you know that dist(root, a) > dist(root, father_of_a)

This way you can build a constructive algorithm to find an answer

for the root, you know that dist(root, root) == 0 for the other nodes: dist(root, a) = w(edge from father_of_a to a) + dist(root, father_of_a) so w(edge from father_of_a to a) = dist(root, a) — dist(root, father_of_a)

Since you know the values for the distances (following that method in the beginning), you now know how to calculate w.

This value must be positive, since dist(root, a) > dist(root, father_of_a). If at some point you have a negative value, that's also an indication that finding an answer is impossible.

My solution, for reference: https://mirror.codeforces.com/contest/1611/submission/136944858