Tutorial for Codeforces 1286B/1287D

Solution #

First, if $c_i$ is greater than the size of the subtree of node $i$ , there’s no answer.

For each node we build an array containing all the nodes from the its subtree bottom-up, and these nodes are in ascending order of value written on them (i.e. $a_i$ ) even though we don’t know the exact value for now. We only care about their relative relationship. The next question is how to combine all the arrays of the children. The answer is quite simple: we can simply glue then together since each subtree is independent. The last step is to put the node in the array. Since we already know $c_i$ , so $i$ should be put in the $c_i$ -th position of the array.

Now we have that array containing all the nodes. Let’s call it $order$ . We can assign $1,2,3,\dots$ to $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;
}

Tutorial for Codeforces 1286B/1287D - Numbers on Tree

Solution #

Code #