Numbers on Tree (Codeforces 1286B)
Tags: Greedy, 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):
import sys, threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
INF = 10 ** 10

def main():
    """"""
    n = get_int()
    childs = [[] for _ in range(n)]
    smalls = []
    for i in range(n):
        (p, c) = get_list()
        smalls.append(c)
        if p > 0:
            childs[p - 1].append(i)
        else:
            root = i

    def dfs(root):
        res = []
        for child in childs[root]:
            res += dfs(child)
        if smalls[root] > len(res):
            return
        res.insert(smalls[root], root)
        return res
    costs = [0] * n
    try:
        for (i, ele) in enumerate(dfs(root)):
            costs[ele] = i + 1
        print('YES')
        print(' '.join(map(str, costs)))
    except:
        print('NO')
import sys
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
threading.Thread(target=main).start()

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

def build(k):
    children = []
    for i in adj[k]:
        children += build(i)
    if C[k] > len(children):
        raise ValueError
    children.insert(C[k], k)
    return children
n = int(input())
adj = {i: [] for i in range(n + 1)}
C = [0 for i in range(n + 1)]
for i in range(1, n + 1):
    (p, c) = map(int, input().split())
    adj[p].append(i)
    C[i] = c
ans = [0 for _ in range(n + 1)]
try:
    for (val, i) in enumerate(build(0)):
        ans[i] = val + 1
    print('YES')
    print(*ans[1:])
except ValueError:
    print('NO')