CodeForces - 1287D Numbers on Tree

传送门：CodeForces - 1287D

题目描述

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$.

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!

输入描述

The first line contains an integer n $(1≤n≤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≤p_i≤n; 0≤c_i≤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.

输出描述

If a solution exists, in the first line print “YES”, and in the second line output n integers ai $(1≤a_i≤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$.

思路分析

大概意思就是，给你一个树，每个点有一个$c$,表示这棵树的子树中有多少个子节点比它的权值小，让你构造出所有点的权值。

样例输入

3
2 0
0 2
2 0

样例输出

YES
1 2 1 

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e5+10;

int c[N],ans[N];
vector<int>e[N];

vector<int> dfs(int u){
    vector<int>res;
    for(auto v:e[u]){
        vector<int>temp=dfs(v);
        res.insert(res.end(),all(temp));
    }
    if(c[u]>res.size()){
        puts("NO");
        exit(0);
    }
    res.insert(res.begin()+c[u],u);
    return res;
}

int main() {
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif

    int n,rt;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x>>c[i];
        if(x==0)
            rt=i;
        e[x].pb(i);
    }
    vector<int>s=dfs(rt);
    puts("YES");
    for(int i=0;i<s.size();i++)
        ans[s[i]]=i+1;
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";



    return 0;
}