题意:
给出n个节点的树，每个节点的属性c i表示子树中权值小于该节点的个数。问能否确定树的每个节点的权值
思路：
比较特殊的构造就是让权值为[ 1 , n ]，这样可以消除相同数的影响。
没有相同数的话，一个节点的权值等于当前未被选择过的权值中第c i + 1大的数。由于n只有2000，所以在这部分可以暴力找。
d f s处理就好了。
如果说某个节点的子树大小< =属性值，那么是无解的。
代码：
// Problem: B. Numbers on Tree // Contest: Codeforces - Codeforces Round #612 (Div. 1) // URL: https://codeforces.com/problemset/problem/1286/B // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=2100,maxm=1e6+7,mod=1e9+7; const int inf=0x3f3f3f3f; vector<int>g[maxn]; int ans[maxn],c[maxn],n,root,flag=1,siz[maxn]; vector<int>nums; bool vis[maxn]; void dfs(int u){ int id=c[u]+1; siz[u]=1; //cout<<u<<" "<<nums.size()<<" "<<id<<endl; int cnt=0; for(int i=1;i<=n;i++){ if(!vis[i]){ cnt++; if(cnt==id){ ans[u]=i; vis[i]=1; break; } } } for(int i=0;i<g[u].size();i++){ int j=g[u][i]; // cout<<j<<" "<<u<<endl; dfs(j); siz[u]+=siz[j]; } if(c[u]>=siz[u]){ flag=0;return ; } return ; } int main(){ n=read; rep(i,1,n){ int fa=read;c[i]=read; g[fa].push_back(i); if(fa==0) root=i; } rep(i,1,n){ if(g[i].size()==0){ if(c[i]){ puts("NO");return 0; } } } dfs(root); //cout<<flag<<endl; if(flag){ puts("YES"); rep(i,1,n) printf("%d ",ans[i]); } else puts("NO"); return 0; } /* 3 2 0 0 2 2 0 */
