CF1286B Numbers on Tree

神仙构造题

题解：

这题的构造过于神仙。。。所以让我们直接观察（部分省略的）代码qwq

vector<int> q;
int dfs(int x){
    int sz=1;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        sz+=dfs(y);
    }
    if(sz<=ned[x]){
        puts("NO");
        exit(0);
    }
    q.insert(q.begin()+ned[x],x);
    return sz;
}
signed main(){
    dfs(rt);
    for(int i=0;i<q.size();i++) ans[q[i]]=i+1;
}

代码应该很好理解。。。

那么为什么这么做是对的呢？

首先no的情况应该很容易判断

其次就用到了贪心的思想，考虑照这种方法insert的话，insert的pos前面的节点都将会是这个root的（部分）子树，然后就是个简单的贪心，强制使他的数字比前面的数都大就行了

那为啥两棵子树不会互相影响呢？因为遍历到一棵新子树时是从叶子开始insert的，而叶子想要合法就一定会被insert在最前面，于是不相关的部分就都被挤到后面，不用再考虑了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=2005;
int en,h[N],ans[N],n,ned[N],rt;
vector<int> q;

struct edge{
    int n,v;
}e[N];

void add(int x,int y){
    e[++en]=(edge){h[x],y};
    h[x]=en;
}

int dfs(int x){
    int sz=1;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        sz+=dfs(y);
    }
    if(sz<=ned[x]){
        puts("NO");
        exit(0);
    }
    q.insert(q.begin()+ned[x],x);
    return sz;
}

signed main(){
    read(n);
    for(int i=1,x;i<=n;i++){
        read(x);read(ned[i]);
        if(!x) rt=i;
        else add(x,i);
    }
    dfs(rt);
    puts("YES");
    for(int i=0;i<q.size();i++) ans[q[i]]=i+1;
    for(int i=1;i<=n;i++) write(ans[i]),putchar(' ');
}