传送门
题意: 现在有一棵树 每个点有一个ci和ai
ai为点权,ci代表i的子树中点权aj <ai 的个数
现在给你这棵树的形状和每个点的ci
构造所有点的ai
n<2000
思路:
ci大于子节点个数时显然不能构造出解;
假设当前节点有m个子节点 该点的Ci为k;
那么 就相当于将该节点的 子节点分为两部分
k个节点的权值小于ai的 m-k个节点的权值大于ai
dfs即可
#include<bits/stdc++.h>
using namespace std;
typedef long long L;
vector<int>vec[2010];
vector<int>ans,ans1,ans2;
int a[2010],c[2010];
vector<int> dfs(int u)
{
vector<int>ans1,ans2;
int len=vec[u].size();
for(int i=0;i<len;i++){
int to=vec[u][i];
vector<int>tmp;
tmp=dfs(to);
for(int j=0;j<tmp.size();j++) ans1.push_back(tmp[j]);
}
if(ans1.size()<c[u]){
cout<<"NO\n";
exit(0);
}
for(int i=0;i<c[u];i++){
ans2.push_back(ans1[i]);
}
ans2.push_back(u);
for(int i=c[u];i<ans1.size();i++){
ans2.push_back(ans1[i]);
}
return ans2;
}
int main(){
ios::sync_with_stdio(0);cout.tie(0);
//cout<<vec[1].size();
int n,root;cin>>n;
for(int i=1;i<=n;i++){
int p;
cin>>p>>c[i];
if(p!=0)
vec[p].push_back(i);
else
root = i;
}
ans=dfs(root);
cout<<"YES\n";
for(int i=0;i<ans.size();i++){
a[ans[i]]=i+1;
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<"\n";
}