题解 P5659 【树上的数【民间数据】】

· · 题解

考场想出来 n^2 没调出来，自闭了。

首先考虑一条链的情况。

对于一个点 x ，我们观察一下它上面的数字变动情况。可以发现无论我们先删左边还是先删右边，原来它上面的数字一定会被搬运到了其中一个方向，同时另一个方向一定又过来了一个数，此外还有一个数字反向经过了 x 。

也就是下面这种情况（这里是先删除右边那条边）：

接下来我们考虑节点度数不是 2 的情况。

在上面的情况中，经过 x 的 c 实际上确定了应该先删除右边再删除左边。

同理如果 x 的度数不是 2 ，那么经过 x 的 c 实际上确定了一个偏序关系，也就是哪条边需要在哪条边之后被删除。

当我们把所有的情况画出来的时候，结果就变得有意思了起来：

当我们按照 c-1,c-2,c-3,c-4,c-5 的顺序依次删除的时候，原先位于 x 上的数被搬运到了 1 号点的方向（注意只是方向，不一定被搬运到 1 号点），同时还有 4 个数 c_1,c_2,c_3,c_4 经过了 x ，最后从 5 号点的方向又过来了一个数。

概括一下就是对于一个点 x ，把所有经过它的数字连到一起，刚好把它的所有出边连成一条偏序链。

有了这个，我们就可以贪心了。假设我们需要将 u 上面的数搬运到 v 上面，我们需要判断 u 到 v 这条路径是否合法。

对于 u ：

对于 v ，可以对称来看：

对于 u 到 v 的路径上的其它点（记为 x ）：

为了判定是否形成了一条偏序链，我们可以对每一个点的所有出边开一个双向链表，记录每一个点当前所在偏序链的开头和结尾，这样所有的操作都可以 O(1) 实现。

直接贪心是 n^3 的，但是我们可以直接以 u 为根对整棵树进行一次 dfs ，然后求出所有合法的 v 中节点编号最小的作为这一轮贪心的答案。

时间复杂度 O(n^2) 。

这道题我大概拿出来了 2 个多小时的时间，中间思路错了几次，最后才形成上面那个成熟的思路。由于时间不够只调过了小样例，大样例死循环了，估计再多给我一段时间的话 Day1 就能 AK 了？（其实 Day2 也是最后十几分钟猜出了 T2 结论没写， 所以给我 5 个小时大概能口胡 AK CSP？ 然而这和我今年撑死过不了500又有什么关系呢）

考后调好的代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Edge
{
    int to;
    int nxt;
}e[10005];
int t,n,m,edgenum,head[2005],p[2005],d[2005],d1[2005],d2[2005],from[2005],too[2005],pa[2005];
int edge[2005][2005],en[2005][2005],st[2005][2005];
bool flag[2005];
/*
数组含义如下：
p[i]表示i这个数字在哪个节点上
d[i]表示第i个点还有多少条出边没有被走过
d1[i]表示第i个点还有多少条出边只被一个数字走进来了一次
d2[i]表示第i个点还有多少条出边只被一个数字走出去了一次
from[i]表示搬运到第i个点的数字是从哪个方向来的
too[i]表示第i个点上的数字被搬运到了哪个方向
edge[i][j]表示i到j的这一条边是没有被数字经过(-1)，只有一个数字从i到j经过了一次(i)，只有一个数字从j到i经过了一次(j)，还是被两个数字来回经过了(0)
st[i][j]表示对i号点来说，(i,j)这条边当前所在的偏序链的开头指向哪个节点
en[i][j]表示对i号点来说，(i,j)这条边当前所在的偏序链的结尾指向哪个节点
flag[i]表示i号点是否可行
*/
void add(int u,int v)
{
    e[++edgenum].to=v;
    e[edgenum].nxt=head[u];
    head[u]=edgenum;
}
void dfs(int node,int root)
{
    for(int hd=head[node];hd;hd=e[hd].nxt)
    {
        int to=e[hd].to;
        if(to==pa[node])continue;
        pa[to]=node;
        flag[to]=1;
        if(node!=root)//如果node不是根，我们需要判断这条边经过node是否合法
        {
            if(edge[pa[node]][node]==pa[node]||edge[node][to]==node)flag[to]=0;
            if(edge[pa[node]][node]==0||edge[node][to]==0)flag[to]=0;//这两行判断的是这条边是否已经被别的数字沿相同方向走了一次
            if(en[node][to]==from[node]&&st[node][pa[node]]==too[node]&&d2[node]+d1[node]+d[node]*2-2>0)flag[to]=0;//如果已经形成了偏序链，是否还有别的出边不在这条链上
            if(en[node][to]==pa[node])flag[to]=0;//经过node的数字是否形成了一个环
        }
        else//否则，我们需要判断这条边能否从node出发到to
        {
            if(edge[node][to]==node)flag[to]=0;
            if(edge[node][to]==0)flag[to]=0;//这条边是否已经被别的数字沿相同方向走了一次
            if(from[node])
            {
                if(en[node][to]==from[node]&&d[node]+d1[node]+d2[node]-1!=0)flag[to]=0;//如果已经形成了偏序链，是否还有别的出边不在这条链上
            }
        }
        flag[to]&=flag[node];//如果node不可行，那么to也一定不可行
        dfs(to,root);
    }
    //下面判断的是这条链能否到node终止
    if(node==root)flag[node]=0;//自己到自己肯定不合法
    else
    {
        if(from[node])flag[node]=0;//已经有了入边肯定不合法
        if(too[node])
        {
            if(en[node][too[node]]==pa[node]&&d[node]+d1[node]+d2[node]-1!=0)flag[node]=0;//如果已经形成了偏序链，是否还有别的出边不在这条链上
        }
    }
}
int main()
{
//  freopen("tree.in","r",stdin);
//  freopen("tree.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        edgenum=0;
        for(int i=1;i<=n;i++)head[i]=from[i]=too[i]=d[i]=d1[i]=d2[i]=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&p[i]);
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
            d[u]++,d[v]++;
            edge[u][v]=edge[v][u]=-1;
            en[u][v]=st[u][v]=v;
            en[v][u]=st[v][u]=u;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)pa[j]=0;
            flag[p[i]]=1;
            dfs(p[i],p[i]);
            int res=0;
            for(int j=1;j<=n;j++)
            {
                if(flag[j])
                {
                    res=j;
                    break;
                }
            }
            printf("%d ",res);
            from[res]=pa[res];
            while(pa[res]!=p[i])//从res开始一路更新它的所有祖先
            {
                if(edge[pa[res]][res]==-1)
                {
                    edge[pa[res]][res]=edge[res][pa[res]]=pa[res];
                    d[res]--,d2[res]++;
                    d[pa[res]]--,d1[pa[res]]++;
                }
                else
                {
                    edge[pa[res]][res]=edge[res][pa[res]]=0;
                    d1[res]--;
                    d2[pa[res]]--;
                }
                int t=res;
                res=pa[res];
                st[res][en[res][t]]=st[res][pa[res]];
                en[res][st[res][pa[res]]]=en[res][t];//链表的插入
            }
            if(edge[pa[res]][res]==-1)
            {
                edge[pa[res]][res]=edge[res][pa[res]]=pa[res];
                d[res]--,d2[res]++;
                d[p[i]]--,d1[p[i]]++;
            }
            else
            {
                edge[pa[res]][res]=edge[res][pa[res]]=0;
                d1[res]--;
                d2[p[i]]--;
            }
            too[p[i]]=res;
//          华丽的debug：
//          printf("%d:%d\n",i,res);
//          printf("pa:");
//          for(int j=1;j<=n;j++)printf("%d ",pa[j]);
//          printf("\n");
//          printf("from:");
//          for(int j=1;j<=n;j++)printf("%d ",from[j]);
//          printf("\n");
//          printf("to:");
//          for(int j=1;j<=n;j++)printf("%d ",too[j]);
//          printf("\n");
//          printf("d:");
//          for(int j=1;j<=n;j++)printf("%d ",d[j]);
//          printf("\n");
//          printf("d1:");
//          for(int j=1;j<=n;j++)printf("%d ",d1[j]);
//          printf("\n");
//          printf("d2:");
//          for(int j=1;j<=n;j++)printf("%d ",d2[j]);
//          printf("\n");
        }
        printf("\n");
    }
    return 0;
}

update:

程序发下来后调了有 20 分钟就 A 掉了……不过貌似能过掉链的数据？