CodeForces 1286B/1287D - Numbers on Tree 题解

想明白了以后其实很简单

题解 #

首先，如果 $c_i$ 大于 $i$ 的子树的大小，那么答案不存在。

对于每个节点，我们建立一个数组，这个数组包含这个节点所有子树的节点，按照 $a_i$ 的大小排序（虽然我们现在还不知道 $a_i$ 的具体数值，我们只关心相对大小关系）。下一个问题就是如何组合子节点的数组，答案其实很简单：直接拼起来就可以了，因为每个子树是互相独立的。最后一步就是把当前的节点放进去，因为 $c_i$ 是已知的所以数组的第 $c_i$ 个数应该是 $i$ .

现在我们有了包含所有节点的数组 $order$ ，我们把 $1,2,3,\dots$ 赋给 $order_1,order_2,order_3,\dots$ 就行了。

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;
}