想明白了以后其实很简单
题解 #
首先,如果大于的子树的大小,那么答案不存在。
对于每个节点,我们建立一个数组,这个数组包含这个节点所有子树的节点,按照的大小排序(虽然我们现在还不知道的具体数值,我们只关心相对大小关系)。下一个问题就是如何组合子节点的数组,答案其实很简单:直接拼起来就可以了,因为每个子树是互相独立的。最后一步就是把当前的节点放进去,因为是已知的所以数组的第个数应该是.
现在我们有了包含所有节点的数组,我们把 赋给 就行了。
Code #
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<int>> G;
vector<int> c;
vector<int> dfs(int u){
vector<int> order;
for(auto it:G[u]){
auto child_order=dfs(it);
order.insert(order.end(),all(child_order));
}
if(size(order)<c[u]){
cout<<"NO";
exit(0);
}
order.insert(order.begin()+c[u],u);
return order;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
G.resize(n+1);
c.resize(n+1);
int R;
for1(i,n){
int pa;
cin>>pa>>c[i];
if(pa==0) R=i;
G[pa].push_back(i);
}
auto order=dfs(R);
vector<int> ans(n+1);
forn(i,n) ans[order[i]]=i+1;
cout<<"YES\n";
for1(i,n) cout<<ans[i]<<' ';
return 0;
}