迫真小游戏_牛客博客

$Description$
给定一棵树,每个结点有值 $a_i$ ,确定一个字典序最小的排列,保证在 $i$ 号结点之前每个 $j$ 的深度要小于等于 $a_i$ .

$Solution$
以最小的 $a_i$ 开始找,查找深度小于等于 $a_i$ 且结点标号最小的值,用线段树维护即可.

$Code$

#include<bits/stdc++.h>
#define sc scanf
using namespace std;
const int N=6e5+5;
const int mod=1e9+7;
const int oo=1e9+7;
typedef unsigned long long ull;
typedef long long ll;
template <typename it>int o(it a){cout<<a<<endl;return 0;}
int MIN[N<<2|1];
priority_queue<int,vector<int>,greater<int> >q[N];
void build(int l,int r,int rt){
    if(l==r){
        if(l==1)MIN[rt]=oo;
        else MIN[rt]=q[l].top();
        return;
    }
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
}
void up(int l,int r,int rt,int pos,int val){
    if(l==r&&l==pos){
        MIN[rt]=val;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid)up(l,mid,rt<<1,pos,val);
    else up(mid+1,r,rt<<1|1,pos,val);
    MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
}
int Q(int l,int r,int rt,int R){
    if(r<=R)return MIN[rt];
    int mid=l+r>>1;
    int ans=oo;
    if(R>mid)ans=min(ans,Q(mid+1,r,rt<<1|1,R));
    ans=min(ans,Q(l,mid,rt<<1,R));
    return ans;
}
int n,a[N],depth=0;
struct edge{
    int u,v,next;
}g[N<<1];
int tot=0;
int head[N];
int ans[N],pos[N];
set<int>p;
int dep[N],s[N],b[N];
void add(int u,int v){
    g[++tot]={u,v,head[u]};
    head[u]=tot;
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    depth=max(depth,dep[u]);
    for(int i=head[u];~i;i=g[i].next)if(g[i].v^fa)dfs(g[i].v,u);
}
int main(){
    //freopen("in.txt","r",stdin);
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        sc("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    sc("%*d");ans[1]=1;int t=1;
    for(int i=2;i<=n;i++){sc("%d",&a[i]);if(a[i]>=depth)a[i]=depth;s[a[i]]++;p.insert(a[i]);}
    for(int i=2;i<=n;i++)q[dep[i]].push(i),pos[i]=dep[i];
    build(1,depth,1);
    while(t<=n){
        if(t==n)break;
        int val=*p.begin();
        int mi=Q(1,depth,1,val);
        if(mi==oo)break;
        ans[++t]=mi;
        q[pos[mi]].pop();
        if(q[pos[mi]].empty())
        up(1,depth,1,pos[mi],oo);
        else up(1,depth,1,pos[mi],q[pos[mi]].top());
        s[a[mi]]--;
        if(s[a[mi]]==0)p.erase(a[mi]);
    }
    for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);
}