题目传送门pwp

$10\ pts$ :

$O(n!)$ 做法不多说。


$35\ pts$ :

考虑菊花图的做法。

假设度数为 $n-1$ 的节点编号为 $u$ ,$n-1$ 条边分别是 $(u,v_1),(u,v_2),\cdots,(u,v_{n-1})$ 。现在我们有一个长度为 $n-1$ 的排列 $p_1,p_2\cdots p_{n-1}$ ,如果依次删除 $(u,v_{p_1}),(u,v_{p_2}),\cdots,(u,v_{p_{n-1}})$ ,就会使得 $u$ 上的数到 $v_{p_1}$ ,$v_{p_1}$ 上的数到 $v_{p_2}$ ....... 最后 $v_{p_{n-1}}$ 上的数会到 $u$ 。

然后建一个图,图中有 $n-1$ 个节点,其中一条边 $u\rightarrow v$ 表示原树中第 $u$ 条边要比第 $v$ 条边先删除,那么对于一个删边顺序,将边依次删完后,一定会使得新图中留下一个长度为 $n-1$ 的链。

接下来考虑如何求答案。

显然最优方案为从小到大枚举数字 $i$ ,将其移动到当前可以移动到且移动过程不会影响前 $i-1$ 个数字的所有点中编号最小的。

那么对于当前的数字 $i$ 和钦定的目标点 $y$ ,怎么判断 $i$ 可以合法的移动到 $y$ 呢?

可以发现,这一过程需要用到(设 $i$ 的起始点为 $x$) $x\rightarrow u,u\rightarrow y$ 两条边,并且一定是删除 $x\rightarrow u$ 后立刻删除 $u\rightarrow y$ ,不然的话 $i$ 移动到 $u$ 后就不会移动到 $y$ 了。若 $x\rightarrow u$ 的编号为 $l_1$ ,$u\rightarrow y$ 的编号为 $l_2$ ,那么就会使得新图中新增 $l_1\rightarrow l_2$ 这条边。

但是可能会出现 $l_1\rightarrow l_2,l_2\rightarrow l_3,l_3 \rightarrow l_1$ 的情况,显然这样是不合法的,用并查集维护一下新图的连边情况即可。


$60\ pts$ :

考虑链的做法。

主要需要考虑将点 $u$ 上的数字 $i$ 运送到 $v$ 的过程是否合法,在链中,这条路程是这样的:

$$ u\rightarrow p_1\rightarrow p_2\rightarrow \cdots \rightarrow p_m\rightarrow v $$

显然 $u\rightarrow p_1$ 要在 $p_1\rightarrow p_2$ 前面删除,$p_1\rightarrow p_2$ 要在 $p_2\rightarrow p_3$ 前面删除........$p_{m-1}\rightarrow p_{m}$ 要在 $p_m\rightarrow v$ 前面删除,这样又可以建出新图了。

需要注意的是,因为链上每个节点的度数为 $2$ ,设 $u$ 的另一条边为 $to_u\rightarrow u$ ,$v$ 的另一条边为 $v\rightarrow to_v$ ,那么需要注意的有两点:

  • $u\rightarrow p_1$ 必须在 $to_u\rightarrow u$ 之前删除,不然 $u$ 上的数字 $i$ 会跑到 $to_u$ 上面去。
  • $p_m\rightarrow v$ 必须在 $to_v\rightarrow v$ 之后删除,不然本来运到 $v$ 上的数字 $i$ 会运到 $to_v$ 上面去。

中间的点也需要保证满足左边的边比右边的边先删除,这就涉及到了一个哪条边先删除的问题。

于是每个点打 $3$ 个标记即可:该点连出去的第一条边先删除、该点连出去的第二条边先删除、该点的两条边还没有确认谁先删除。


$100\ pts$ :

简单的说,菊花的做法是中间点用并查集维护边的新图,链的做法是每个点维护一个标记,那么满分做法就是每个点都用并查集维护新图。

同样考虑如何判断将点 $u$ 上的数字 $i$ 运送到 $v$ 的过程是否合法。

首先对于每个点 $x$ 开一个并查集维护边的新图,并查集的元素有:

  • $fir$ ($x$ 的所有边中第一个删除的边的编号)
  • $las$ ($x$ 的所有边中最后一个删除的边的编号)
  • $in(k)$ (编号为 $k$ 的边是不是已经被用过了,用处是将该边的另外一端点上的数运到 $x$)
  • $out(k)$ (编号为 $k$ 的边是不是已经被用过了,用处是将 $x$ 上的数运到该边的另外一端点)

对于开始点 $u$ ,假设运输路线的下一个点是 $p_1$ ,$u\rightarrow p_1$ 的编号是 $t$ ,需要满足:

  • $t$ 的 "将 $u$ 点上的数字运送到 $p_1$" 的机会没有使用过,即对于 $u$ 的并查集来说,$out(t)=0$ 。
  • 如果 $u$ 的并查集已经钦定了第一个删除的边,那么这个第一个删除的边必须是 $t$ 。(显然如果要将 $u$ 上的数字运送到 $v$ 就必须满足 $u$ 上的数字在删除 $t$ 的之前一直在 $u$ 上)。
  • 如果 $t$ 作为 $u$ 的并查集上第一个删除的边,并且 $t$ 之后紧紧跟着需要删除的边为 $u$ 的并查集上的 $las(las\not= t)$ ,而这个时候 $u$ 的度数必须等于 $2$ (即只包含 $t$ 和 $las$) 。(假设有第三条边 $w$ ,那么既然删除"第一个删除的边"后就要删除"最后一个删除的边",请问 $w$ 的删除顺序是什么?)

于是我们就不清楚 $w$ 怎么删除了,这显然是不合法的。

也就是说,对于 $u$ 并查集中的所有边,最后一定属于一个连通块。

接着考虑结束点 $v$ ,假设运输路线最后一步是 $p_m\rightarrow v$ ,该边的编号为 $h$ ,需要满足:

  • $h$ 的 "将 $p_m$ 点上的数字运送到 $v$" 的机会没有使用过,即对于 $v$ 的并查集来说,$in(h)=0$ 。
  • 如果 $v$ 的并查集已经钦定了最后一个删除的边,那么这个最后一个删除的边必须是 $h$ 。(显然如果要将 $u$ 上的点运送到 $v$ 就必须满足 $u$ 运过来的数字不会被 $v$ 的某一条比 $h$ 后删除的边运走)。
  • 如果 $h$ 作为 $v$ 的并查集上最后一个删除的边,并且 $h$ 之前需要紧跟着需要删除的边为 $v$ 的并查集上的 $fir(fir\not= t)$ ,而这个时候 $u$ 的度数必须等于 $2$ (即只包含 $t$ 和 $las$) 。(假设有第三条边 $w$ ,那么既然删除"第一个删除的边"后就要删除"最后一个删除的边",请问 $w$ 的删除顺序是什么?)

和上面的限制差不多。

最后考虑中间点 $p_i$ ,对于 $p_{i-1}\rightarrow p_i$ (编号为 $t_1$) ,$p_i\rightarrow p_{i+1}$ (编号为 $t_2$) ,需要满足:

  • $t_1$ 的 "将 $p_{i-1}$ 点上的数字运送到 $p_i$" 的机会没有使用过,即对于 $p_i$ 的并查集来说,$in(t_1)=0$ 。
  • $t_2$ 的 "将 $p_{i}$ 点上的数字运送到 $p_{i+1}$" 的机会没有使用过,即对于 $p_i$ 的并查集来说,$out(t_2)=0$ 。
  • 因为对于 $p_i$ 必须满足 $t_1$ 比 $t_2$ 先删除,所以 $t_1$ 不可能是 $p_i$ 并查集中的 $lst$ ,并且 $t_2$ 不可能是 $p_i$ 并查集中的 $fir$ 。
  • 如果之前 $t_1$ 和 $t_2$ 就在 $p_i$ 的并查集中有过一条边,但是需要满足 $t_1$ 有 $in$ 的机会,$t_2$ 也有 $out$ 的机会,那么之前的这一条边必然是用去了 $t_1$ 的 $out$ 机会和 $t_2$ 的 $in$ 机会,也就是说之前的那条路径是先删除 $t_2$ 将数字运进来再用 $t_1$ 将数字运出去。

    也就是说之前的那条路径的条件是先删除 $t_2$ 再删除 $t_1$ ,而这一次要求先删除 $t_1$ 再删除 $t_2$ ,显然与之前矛盾。

  • 如果 $p_i$ 的并查集已经有了 $fir$ 和 $lst$ ,并且都不等于 $t_1$ 和 $t_2$ 。如果 $fir$ 和 $t_1$ 已经属于一个连通块,$t_2$ 和 $lst$ 已经属于一个连通块,现在需要将 $t_1$ 和 $t_2$ 之间连一条边。

    显然上文已经讲了,$fir$ 和 $lst$ 之间必须包含所有的边,如果当前 $t_1\&fir$ 的连通块包含的边数和 $t_2\&lst$ 的连通块包含的边数相加小于 $p_i$ 的度数,那么一定有一些边不在最后的连通块中。假设 $w$ 的不在最后的连通块中,请问 $w$ 的删边顺序是什么?

    所以如果 $fir$ 和 $t_1$ 已经是一个连通块了,并且 $t_2$ 和 $lst$ 也是一个连通块了,需要满足两个连通块大小加起来为 $p_i$ 的度数。

最后找到了 $u$ 最好的终点 $v$ ,只需要更新路径上的所有点的并查集即可。

  • 对于开始点 $u$ ,确认了 $u$ 并查集中的 $fir$ 。
  • 对于结束点点 $v$ ,确认了 $v$ 并查集中的 $lst$ 。
  • 对于中间点点 $p_1$ ,合并 $t_1$ 和 $t_2$ 所在的集合。

然后细节有点多,毕竟限制条件很多。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=2e3+5;
int T,n,st[N],cnt,head[N];
struct Edge {int nxt,to;} G[N<<1];

struct DSU {
    bool in[N],out[N];
    int fa[N],tot,fir,las;
    inline void clear() {
        tot=fir=las=0;
        for(int i=1;i<=n;++i) fa[i]=i,in[i]=out[i]=1;
    }
    int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
    inline bool check(int x,int y) {return find(x)==find(y);}
    inline void merge(int x,int y) {fa[find(x)]=find(y);}
}dsu[N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}
inline void addedge(int u=0,int v=0) {
    IN(u),IN(v);
    G[++cnt]=(Edge){head[u],v},head[u]=cnt,++dsu[u].tot;
    G[++cnt]=(Edge){head[v],u},head[v]=cnt,++dsu[v].tot;
}

int solve(int u,int lst) { /*lst=last_edge*/
    int ans=n+1;
    if(lst&&(!dsu[u].las||dsu[u].las==lst)&&dsu[u].in[lst]) /*u(end)*/
        if(!dsu[u].fir||dsu[u].tot==1||!dsu[u].check(dsu[u].fir,lst)) ans=u;
    for(int i=head[u];i;i=G[i].nxt) {
        int nxt=(i>>1); /*nxt_edge*/
        if(nxt==lst) continue;
        if(!lst) { /*u(begin)*/
            if(!dsu[u].out[nxt]) continue;
            if(dsu[u].fir&&dsu[u].fir!=nxt) continue;
            if(dsu[u].las&&dsu[u].tot>1&&dsu[u].check(nxt,dsu[u].las)) continue;
            ans=min(ans,solve(G[i].to,nxt));
        } else { /*u(middle)*/
            if(!dsu[u].in[lst]||!dsu[u].out[nxt]) continue;
            if(lst==dsu[u].las||nxt==dsu[u].fir||dsu[u].check(lst,nxt)) continue;
            if(dsu[u].fir&&dsu[u].las&&dsu[u].tot>2)
                if(dsu[u].check(dsu[u].fir,lst)&&dsu[u].check(nxt,dsu[u].las)) continue;
            ans=min(ans,solve(G[i].to,nxt));
        }
    }return ans;
}

bool update(int u,int end,int lst) { /*lst=last_edge*/
    if(u==end) {dsu[u].las=lst;return true;}
    for(int i=head[u];i;i=G[i].nxt) {
        int nxt=(i>>1),v=G[i].to;
        if(nxt==lst||!update(v,end,nxt)) continue;
        if(!lst) dsu[u].fir=nxt;
        else --dsu[u].tot,dsu[u].merge(lst,nxt),dsu[u].in[lst]=dsu[u].out[nxt]=0;
        return true;
    }return false;
}

int main() {
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    IN(T);
    while(T--) {
        IN(n);
        memset(head,0,sizeof(head)),cnt=1;
        for(int i=1;i<=n;++i) IN(st[i]),dsu[i].clear();
        for(int i=1;i<n;++i) addedge();
        if(n==1) {puts("1");continue;}
        for(int i=1;i<=n;++i) {
            int end=solve(st[i],0);
            update(st[i],end,0),printf("%d ",end);
        }puts("");
    }return 0;
}
最后修改:2019 年 12 月 15 日 10 : 06 AM