Numbers on Tree (Codeforces 1287D)
Tags: Others, trees

Evlampiy was gifted a rooted tree. The vertices of the tree are numbered from $$$1$$$ to $$$n$$$. Each of its vertices also has an integer $$$a_i$$$ written on it. For each vertex $$$i$$$, Evlampiy calculated $$$c_i$$$ — the number of vertices $$$j$$$ in the subtree of vertex $$$i$$$, such that $$$a_j < a_i$$$. Illustration for the second example, the first integer is $$$a_i$$$ and the integer in parentheses is $$$c_i$$$After the new year, Evlampiy could not remember what his gift was! He remembers the tree and the values of $$$c_i$$$, but he completely forgot which integers $$$a_i$$$ were written on the vertices.Help him to restore initial integers!

Input: The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 2000)$$$ — the number of vertices in the tree.The next $$$n$$$ lines contain descriptions of vertices: the $$$i$$$-th line contains two integers $$$p_i$$$ and $$$c_i$$$ ($$$0 \leq p_i \leq n$$$; $$$0 \leq c_i \leq n-1$$$), where $$$p_i$$$ is the parent of vertex $$$i$$$ or $$$0$$$ if vertex $$$i$$$ is root, and $$$c_i$$$ is the number of vertices $$$j$$$ in the subtree of vertex $$$i$$$, such that $$$a_j < a_i$$$.It is guaranteed that the values of $$$p_i$$$ describe a rooted tree with $$$n$$$ vertices.

Output: If a solution exists, in the first line print "YES", and in the second line output $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq {10}^{9})$$$. If there are several solutions, output any of them. One can prove that if there is a solution, then there is also a solution in which all $$$a_i$$$ are between $$$1$$$ and $$$10^9$$$.If there are no solutions, print "NO".


Sample Inputs:
3
2 0
0 2
2 0

5
0 1
1 3
2 1
3 0
2 0

Sample Outputs:
YES
1 2 1

YES
2 3 2 1 2

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
n = int(input())
c = [0 for i in range(n + 1)]
a = [0 for i in range(n + 1)]
g = [[] for i in range(n + 1)]

def dfs(x):
    List = []
    for i in g[x]:
        List += dfs(i)
    if c[x] > len(List):
        raise ValueError
    List.insert(c[x], x)
    return List
for i in range(1, n + 1):
    (pi, ci) = list(map(int, input().split(' ')))
    c[i] = ci
    g[pi].append(i)
try:
    ans = dfs(0)
    print('YES')
    for i in range(0, n + 1):
        a[ans[i]] = i
    for i in range(1, n + 1):
        print(a[i], end=' ')
except ValueError:
    print('NO')

Solution (Python):
""""""
from sys import setrecursionlimit
setrecursionlimit(1000000)
n = int(input())
graph = [[] for _ in range(n + 1)]
ci = [0]

def solve(x):
    rst = []
    for s in graph[x]:
        rst.extend(solve(s))
    if len(rst) < ci[x]:
        raise ValueError
    rst.insert(ci[x], x)
    return rst
for i in range(1, n + 1):
    (p, c) = map(int, input().split())
    graph[p].append(i)
    ci.append(c)
try:
    ans = solve(graph[0][0])
except ValueError:
    print('NO')
else:
    print('YES')
    for i in range(1, n + 1):
        print(ans.index(i) + 1, end=' ')

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(1000000)
n = int(input())
graph = [[] for _ in range(n + 1)]
ci = [0]

def solve(x):
    rlt = []
    for v in graph[x]:
        rlt.extend(solve(v))
    if len(rlt) < ci[x]:
        raise ValueError
    rlt.insert(ci[x], x)
    return rlt
for i in range(1, n + 1):
    (p, c) = map(int, input().split())
    graph[p].append(i)
    ci.append(c)
try:
    ans = solve(graph[0][0])
except ValueError:
    print('NO')
else:
    print('YES')
    for i in range(1, n + 1):
        print(ans.index(i) + 1, end=' ')