D. Numbers on Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Evlampiy was gifted a rooted tree. The vertices of the tree are numbered from 1to n. Each of its vertices also has an integer ai written on it. For each vertex i, Evlampiy calculated ci — the number of vertices j in the subtree of vertex i, such that aj<ai.Illustration for the second example, the first integer is aiand the integer in parentheses is ci
After the new year, Evlampiy could not remember what his gift was! He remembers the tree and the values of ci, but he completely forgot which integers aiwere written on the vertices.
Help him to restore initial integers!
Input
The first line contains an integer n(1≤n≤2000)— the number of vertices in the tree.
The next nlines contain descriptions of vertices: the i-th line contains two integers pi and ci (0≤pi≤n; 0≤ci≤n−1), where pi is the parent of vertex i or 0 if vertex i is root, and ci is the number of vertices j in the subtree of vertex i, such that aj<ai.
It is guaranteed that the values of pidescribe 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 ai (1≤ai≤109). 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 ai are between 1 and 109.
If there are no solutions, print “NO”.

递归写法：
借鉴别人的思路，容易证明，如果存在解，那么一定可以用1~n以内的数表示结果。可以用n个数，来填满这n个位置，且每个位置的数不同。由于有限制，那么可以从根节点开始填数，每次用一个数，标记，下次不用。每次for循环，找到满足c[i]的值。一直递归下去直到找到所有的解。然后在回溯的时候判断是否有解，即要求c[i]的值应不大于i节点的子树的节点总数。因此，回溯的时候计算每个节点的总数，进行判断。

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,c[N],ans[N],sub[N];
bool vis[N],f;
vector<int>pic[N];
void dfs(int num)
{
    if(!f)
        return;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
            cnt++;
        if(cnt==c[num]+1)
        {
            ans[num]=i;
            vis[i]=1;
            break;
        }
    }
    for(int i=0;i<pic[num].size();i++)
    {
        dfs(pic[num][i]);
        sub[num]+=sub[pic[num][i]];
    }
    if(sub[num]<c[num])
    {
        f=0;
        return;
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int root,p;
        for(int i=0;i<=n;i++)
            pic[i].clear();
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p,&c[i]);
            if(p==0)
                root=i;
            else
                pic[p].push_back(i);
        }
        for(int i=1;i<=n;i++)
            sub[i]=pic[i].size();
        f=1;
        dfs(root);
        if(f)
        {
            printf("YES\n");
            for(int i=1;i<=n;i++)
                printf("%d%c",ans[i],i==n?'\n':' ');
        }
        else
            printf("NO\n");
    }
    return 0;
}