更好的阅读体验

Statement

给定一棵大小为 $n$ 的数，初始时每个节点上都有一个 $1\sim n$ 的数字，且每个 $1\sim n$ 的数字都只 恰好 在一个节点上出现。

进行 恰好 $n-1$ 次删边操作，每次操作需要选一条 未被删去的边 ，交换两个端点的数字，并删边。

删完后，按数字 $1\sim n$ 的顺序将所在节点编号依次排列得到排列 $P_i$ ，求能得到的字典序最小的 $P_i$ .

Thoughts & Solution

这种 “字典序最小”的题一看就很像贪心。

题外话：今天模拟赛也有 “字典序最小”的贪心题，可是我一连胡错了两次，最后思路对了还调了半天（

要想贪心，肯定是让某个小编号尽可能地在最后的排列中得到小的权值。那么考虑如何让一个数字最终达到某个特定的位置。

假设现在有一条路径 ：$start\to a\to b\to c\to d\to end$ ，并将这些边从左到右依次标号为 $1,2,3,4,5$ 。

那么，假设我们现在想要把 $start$ 节点上的数字转移到 $end$ 节点上。可以发现：

• 对于所有和 $start$ 相连的边，$1$ 一定是被删除的第一条边（否则 $start$ 原先的权值就被转移没了）
• 对于所有和 $end$ 相连的边，$5$ 一定是被删除的第一条边（否则 $start$ 搞过来的权值就会被转移没了）
• 对于中间点 $a,b,c,d$ ，在它们的删边序列中，$1$ 和 $2$ ，$2$ 和 $3$ ，$3$ 和 $4$ ，$4$ 和 $5$ 一定相邻（防止权值中途被转移走）

由于要前面的数尽可能小，那么枚举填数的时候一定是从小到大的。每次利用以上的性质判断是否能够填到这个位置，直到找到一个能填且最小的位置，并加上这个点给后面的限制。

看到图论里面的限制其实一个很自然的想法就是：连边为限制 ，但是这里的限制是针对边的，那么就可以考虑把边转化成点。

对原树上的每一个点建一张图，图上每个点代表连的一条边，并记录这个点钦定的第一条边和最后一条边。这张图上的一条有向边表示出点在入点之后马上选择。点与点之间建的图是独立的。

考虑什么情况下会出现矛盾。

• 图不能被分割成独立的若干条链（这样就会有一条边后面要连多条边，或是出现环，显然不合法）

• 钦定的第一个点和最后一个点有入/出边（显然不合法）

• 第一个点和最后一个点在同一条链上，但是还有点不在这条链中。（已经形成了完备唯一的删边方案，但是有边还没删）

这些条件的矛盾分别表现为：

• 首先是加边的时候两点不能已经连通，这个并查集判一下就好了；然后出点不能有出边，入点不能有入边，bool 数组记录即可。
• 直接判断
• 这条边会让钦定的起点和终点合并，但是目前不连通的个数还大于 2

然后各种判断就好了。题目很 毒瘤 细节（也有可能是我写烦了），实现时要注意。

代码中有详细的注释，如果发现自己挂了可以看看注释，找找有没有漏掉的条件。

我发现我最近善于把题目写得码农（

//Author: RingweEH
const int N=2010;
int n,pos[N],head[N],tot;   //pos:数字 i 初始节点位置
struct edge
{
    int to,nxt;
}e[N<<1];
struct node_graph       //每个点所建立的图
{
    int fir,las,num,fa[N];      //钦定的第一条边，最后一条，边（点）数，并查集
    bool ine[N],oue[N];     //是否有入/出边
    void clear() { fir=las=num=0; for ( int i=1; i<=n; i++ ) fa[i]=i,ine[i]=oue[i]=0; }
    int find( int x ) { return x==fa[x] ? x : fa[x]=find(fa[x]); }
}g[N];

void add( int u,int v )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; g[u].num++; 
    e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot; g[v].num++;
}

int dfs1( int u,int fro_edge )
{
    int res=n+1;
    if ( fro_edge && (!g[u].las || g[u].las==fro_edge ) )   //还没有终点或者终点就是这条边
    {
        if ( !g[u].oue[fro_edge] && !(g[u].fir && g[u].num>1 && g[u].find(fro_edge)==g[u].find(g[u].fir)) )
        //这条边（点）在这个点的图里面还没有出边，而且不能：
        //有起点，总点数大于1，且已经在一条链里面了
            res=u;
    }
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to,to_edge=i/2;
        if ( fro_edge==to_edge ) continue;      //防止沿着双向边搜回去，tot是从1开始的，所以同一条双向边/2向下取整是一样的
        if ( !fro_edge )        //前面没有链的情况
        {
            if ( !g[u].fir || g[u].fir==to_edge )   //没有钦定起点，或者起点就是当前边
            {
                if ( g[u].ine[to_edge] ) continue;  //如果有入边了就不能当起点
                if ( g[u].las && g[u].num>1 && g[u].find(to_edge)==g[u].find(g[u].las) )
                    continue;   //起点和终点已经在一条链里面了
                res=min( res,dfs1( v,to_edge ) );
            }
            else continue;
        }
        else    //前面有链，往后接的情况
        {
            if ( fro_edge==g[u].las || to_edge==g[u].fir || g[u].find(fro_edge)==g[u].find(to_edge) )
                continue;   //如果上一条链的尾点是终点，那么后面不能接链；如果这条边是起点，那么不能被接；
                //如果已经在一条链上了，也不能被接
            if ( g[u].oue[fro_edge] || g[u].ine[to_edge] ) continue; //已经接过了
            if ( g[u].fir && g[u].las && g[u].num>2 && g[u].find(fro_edge)==g[u].find(g[u].fir) 
                && g[u].find(to_edge)==g[u].find(g[u].las) ) continue;
            //从起点来的链，接上去终点的链，且还有点不在链上
            res=min( res,dfs1( v,to_edge ) );
        }
    }
    return res;
}

int dfs2( int u,int fro_edge,int endpos )
{
    if ( u==endpos ) { g[u].las=fro_edge; return 1; }  //到终点了，使命完成
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to,to_edge=i/2;
        if ( fro_edge!=to_edge )
        {
            if ( dfs2( v,to_edge,endpos ) )     //后面可行
            {
                if ( !fro_edge ) g[u].fir=to_edge;      //前面没有了，这个就是起点
                else
                {   //更新有无出入边的限制，并查集合并
                    g[u].oue[fro_edge]=g[u].ine[to_edge]=1; g[u].num--;
                    g[u].fa[g[u].find(fro_edge)]=g[u].find(to_edge);
                }
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int T=read();
    while ( T-- )
    {
        tot=1; memset( head,0,sizeof(head) );

        n=read();
        for ( int i=1; i<=n; i++ )
            g[i].clear(),pos[i]=read();
        for ( int i=1,u,v; i<n; i++ )
            u=read(),v=read(),add( u,v );

        if ( n==1 ) { printf( "1\n" ); continue; }
        int p;
        for ( int i=1; i<=n; i++ )
        {
            p=dfs1( pos[i],0 ); dfs2( pos[i],0,p );     //1用来搜方案，2用来加限制
            printf( "%d ",p );
        }
        printf( "\n" );
    }

    return 0;
}