Numbers on Tree
Contest: Codeforces Round 612 (Div. 1)
Difficulty rating: 1800
Tags: constructive algorithms, data structures, dfs and similar, graphs, 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 format:
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 format:
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".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3
2 0
0 2
2 0

Example output:
YES
1 2 1

Example input:
5
0 1
1 3
2 1
3 0
2 0

Example output:
YES
2 3 2 1 2

Editorial:
There are several approaches to this problem. We will tell one of them. Note that if $$$c_i$$$ for some vertex is greater than the number of vertices in its subtree, then there is no answer.
Now we prove that we can always build the answer, so that all $$$a_i$$$ will be numbers from $$$1$$$ to $$$n$$$. On those numbers, let's build some structure that supports deleting elements and searching for k-th element. Let's denote by $$$d_v$$$ the number of vertices in the subtree of vertex $$$v$$$. Now iterate over the subtree of $$$v$$$ in the order of the depth first search. Then let's set $$$a_v$$$ = $$$c_v$$$-th element in our structure (and after that delete this element). Firstly, such an element will always exist. This is true because when we examine the vertex $$$v$$$, all vertices in the subtree of this vertex are not yet considered $$$\ Rightarrow$$$ since $$$c_v \ leq d_v$$$ $$$\ Rightarrow$$$ in our structure there are at least $$$c_v$$$ elements. Secondly, the set of all values in the subtree will be a prefix of our structure. If this is true, then the condition that the subtree contains exactly $$$c_v$$$ elements smaller than ours is guaranteed to be satisfied (because all elements from our structure that are smaller than ours are there, and we specifically took the $$$c_v$$$-th element). Let us prove this fact by induction on the size of the tree. For a tree of size $$$1$$$ this is obvious (we always take the first element). Now for size $$$k$$$, we have the root on which the number $$$c_x \ leq k-1$$$ is written. Then when we throw out $$$c_x$$$, and then throw out all the vertices in the subtree, we will remove the prefix of at least $$$k-1$$$ vertices, which means that we will drop all the vertices up to $$$c_x$$$, as well as some prefix of vertices after it, thus in total we'll throw out some prefix of vertices.
Now, we have reduced the problem to dfs and searching for k-order statistics. This can be done in a variety of ways - segment tree, Fenwick tree, sqrt decomposition, Cartesian tree, or a built-in c++ tree.
Code of the author solution with this tree.