2000分的构造题果然超过了我的能力范围，我太菜了
本题的思路是这样的，我们用vector存储父子节点的关系
我们首先递归到子节点，先对子节点求一个答案vector，假如子节点求好了后，我们只需要把父节点插到对应的c值即可
比如c是3，我们就把父节点插到由子节点组成的vector的第四个位置，这样我们就能保证在赋值的时候，有3个比他小
同理一直做就能获得答案，我们最后用1-n来赋值这些操作，这样一定是成立的。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<map> #include<set> #include<vector> using namespace std; typedef long long ll; const int N=5e5+10; const int inf=0x3f3f3f3f; vector<int> num[N]; int root; int x; int c[N]; int ans[N]; vector<int> dfs(int u){ vector<int> res; for(auto x:num[u]){ vector<int> tmp=dfs(x); for(auto a:tmp) res.push_back(a); } if(c[u]>res.size()){ cout<<"NO"<<endl; exit(0); } else{ res.insert(res.begin()+c[u],u); } return res; } int main(){ int n; int i; cin>>n; for(i=1;i<=n;i++){ scanf("%d%d",&x,&c[i]); if(x==0){ root=i; } else{ num[x].push_back(i); } } vector<int> res=dfs(root); for(i=0;i<res.size();i++) ans[res[i]]=i+1; cout<<"YES"<<endl; for(i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl; return 0; }
原文：https://www.cnblogs.com/ctyakwf/p/12288018.html
