题目链接:https://codeforces.com/contest/1287/problem/D
题目大意:
给你一棵树,每个数一个a[i]和c[i]。c[i]:所有i的子节点j满足a[i]>a[j]的节点个数。现在给你n个节点的祖先和c[i]让你分配a[i] (1<=a[i]<=1e9)。
如果不能分配输出NO,如果可以输出YES并且输出每一个点的a[i]。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
struct node{
int to;
int c;
};
vector <node> v[2005];
int vis[2005], f=0;
int pos[2005];
vector<int> dfs(int u, int fa){
vector<int> a;
for(int i=0; i<v[u].size(); i++){
int to=v[u][i].to;
if(to!=fa){
vector<int> b=dfs(to, u);
for(int i=0; i<b.size(); i++){
a.push_back(b[i]);
}
}
}
if(vis[u]>a.size()){//NO
f=1;
}
else{//插入到子节点序列中
a.insert(a.begin()+vis[u], u);
}
return a;
}
int main()
{
int n, root;
scanf("%d", &n);
for(int i=1; i<=n; i++){
int a, b;
scanf("%d%d", &a, &b);
if(a){
v[i].push_back(node{a, b});
v[a].push_back(node{i, b});
}
else{
root=i;
}
vis[i]=b;
}
vector <int> a=dfs(root, -1);
if(f){
printf("NO\n");
return 0;
}
int p=1;
for(int i=0; i<a.size(); i++){//编号
pos[a[i]]=p++;
}
printf("YES\n");
for(int i=1; i<=n; i++){
printf("%d ", pos[i]);
}
return 0;
}