题解 P5659 【树上的数】

· · 题解

\text{D1T3} 树上的数

\text{Descripion}

给定一棵无根树，树上每个点都有一个数，这些数是一个 [1,n] 的全排列。你需要删除所有的边，每次删边会交换边连接的两个点上的数。删完之后，按照点上的数升序排列，使得最后编号组成的字典序最小。

\text{Solution}

考虑一个贪心，我们只会尽量把最小的数送到编号最小的节点。问题转换为，在树中找到一个可行的编号最小的点。现在我们来探讨判断方案是否可行的方法。

事实上我们只需考虑一个点连出的边的删除顺序即可。接下来我们所说的删边序列指的是某一点相邻边的删边序列，并且这个删边序列一开始并没确定，是通过之后可行的运送方案来逐渐确定每条边的先后顺序的。体现在下文中，你可以认为我们实际上是维护了每一个点的若干个删边序列，初始每个点相邻的每条边都是一个单独的删边序列，每次确定了可行的方案后将删边序列合并。我们分别考虑三种情况：

  1. 连入这个点的边和连出这个点的边必须在删边序列中是相邻的，否则刚送进来一个数就会被送到其它地方。

  2. 如果我们通过这两条边将第一条删除的边和最后一条删除的边连在一起，若此时还有边没加入，那么它无法加入删边序列，因为我们保证了删边序列必须是紧接着删除的。

  1. 它连出的边必须在删边序列中的第一个，否则它会先被送到其它地方。
  2. 如果我们通过这条边确认了删边序列的第一条边，若此时删边序列的最后一条边已确定且与删边序列的第一条边同处于一个确定的删边序列中，那么若有边没加入删边序列，那么它无法加入删边序列，理由同上。
  1. 它连入的边必须在删边序列中的最后一个，否则它最后会被送到其它地方。
  2. 如果我们通过这条边确认了删边序列的最后一条边，若此时删边序列的第一条边已确定且与删边序列的最后一条边同处于一个确定的删边序列中，那么若有边没加入这个删边序列，那么它无法加入删边序列，理由同上。

判断就这么解决了，我们来考虑更新。我们只需将方案路径上的每个点按如下方法处理：

然后你会发现，维护这个，我们只需要对每个节点相邻的边开个双向链表，这样以上操作都是 O(1) 的。但是直接枚举每个点进行判断总时间复杂度是 O(n^3) 的，我们考虑以当前起始点为根进行 dfs ，若一个点不满足作为中转点的条件，那么它的子树内的点显然也不满足，回溯时判断该点是否可以作为结束点，而且这样做可以很好的利用之前的信息，总时间复杂度为 O(n^2) ，可以通过本题。

\text{Code}
#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]);
    }
}