CSP2019 树上的数 题解

#include<bits/stdc++.h>
#define REG register
#define MAXN 2005
using namespace std;
inline int read(){
    REG int x(0);
    REG char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
    return x;
}

struct Edge{
    int v,nxt;
}ed[MAXN<<1];
int head[MAXN],cnt;
inline void adde(int u,int v){
    ed[++cnt]=(Edge){v,head[u]};
    head[u]=cnt;
}
inline void add(int u,int v){adde(u,v),adde(v,u);}

int T,n;
int p[MAXN]; // 该数字在哪个节点上
int Len[MAXN][MAXN],Fir[MAXN][MAXN],Lst[MAXN][MAXN],Pre[MAXN][MAXN],Suf[MAXN][MAXN];
// Len ( u , v ) => 这条边所在的链表长度
// Fir ( u , v ) => 这条边所在的链表开头
// Lst ( u , v ) => 这条边所在的链表末尾 
// Pre ( u , v ) => 这条边所在的链表前驱
// Suf ( u , v ) => 这条边所在的链表后继 
int S[MAXN],E[MAXN];
// S ( i ) => 这个点的删边序列开头
// E ( i ) => 这个点的删边序列结尾
int Can[MAXN]; // Can ( i ) => 这个点是否可行 
int fa[MAXN]; // fa ( i ) => 这个点在深搜过程中的父亲 
int deg[MAXN]; // deg ( i ) => 这个点相邻的边 
int Fin[MAXN]; // Fin ( i ) => 这个数最终所在的节点 

void Init(){
    cnt=0;
    n=read();
    for(REG int i=1;i<=n;++i) p[i]=read(),S[i]=E[i]=head[i]=0,deg[i]=0;
    for(REG int i=1;i<n;++i){
        int u=read(),v=read();
        add(u,v);
        ++deg[u],++deg[v];
        Len[u][v]=Len[v][u]=1;
        Fir[u][v]=Lst[u][v]=v,Fir[v][u]=Lst[v][u]=u;
        Pre[u][v]=Pre[v][u]=Suf[u][v]=Suf[v][u]=-1;
    }
}

void Find_Node(int now,int Start){
    for(REG int i=head[now];i;i=ed[i].nxt){
        int v=ed[i].v;
        if(v==fa[now]) continue;
        fa[v]=now;
        bool Can_Mid=true; // 这个点可以作为起始点或中间点 
        if(now^Start){ // 中间点 
            if((~Suf[now][fa[now]])||(~Pre[now][v])) Can_Mid=false; // 条件 1 
            if((Fir[now][fa[now]]==Fir[now][v])&&(Suf[now][fa[now]]^v)) Can_Mid=false; 
            if(S[now]==v) Can_Mid=false;
            if(S[now]&&E[now])
                if(Fir[now][fa[now]]==S[now]&&Lst[now][v]==E[now])
                    if((Len[now][fa[now]]+Len[now][v])^deg[now]) Can_Mid=false;
            // 条件 2
        }
        else{ // 起始点 
            if(S[now]&&(S[now]^v)) Can_Mid=false; // 条件 1 
            if(E[now]&&Lst[now][v]==E[now])
                if(Len[now][v]^deg[now]) Can_Mid=false;
            // 条件 2 
            if(~Pre[now][v]) Can_Mid=false;
        }
        if(Can_Mid) Find_Node(v,Start); 
    }
    // 判断结束点 
    Can[now]=true;
    if(now^Start){
        if(E[now]&&(E[now]^fa[now])) Can[now]=false; // 条件 1
        if(S[now]&&Fir[now][fa[now]]==S[now])
            if(Len[now][fa[now]]^deg[now]) Can[now]=false;
        // 条件 2 
    }
    else Can[now]=false; // 只要有删边，这个数就不能待在原位 
}

void Update_Path(int End,int Start){ 
    int last=End;
    E[End]=fa[End];
    End=fa[End];
    while(End^Start&&End){
        if(Fir[End][fa[End]]^Fir[End][last]){

            int it=last;
            while(~it)
                Fir[End][it]=Fir[End][fa[End]],
                Len[End][it]+=Len[End][fa[End]],
                it=Suf[End][it];
            it=fa[End];
            while(~it)
                Lst[End][it]=Lst[End][last],
                Len[End][it]=Len[End][last],
                it=Pre[End][it];
            Suf[End][fa[End]]=last;
            Pre[End][last]=fa[End];
            last=End;
            End=fa[End];
        }
    }
    S[End]=last;
}

int main(){
    T=read();
    while(T--){
        Init();
        for(REG int i=1;i<=n;++i){
            int pos=p[i];
            memset(Can,false,sizeof Can);
            memset(fa,0,sizeof fa);
            Find_Node(pos,pos);
            int Goal(1);
            for(;Goal<=n;++Goal)
                if(Can[Goal]) break;
            Update_Path(Goal,pos);
            Fin[i]=Goal;
        }
        for(REG int i=1;i<n;++i) printf("%d ",Fin[i]);
        printf("%d\n",Fin[n]);
    }
}