题解 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$ ： - 如果已经有一个数从它搬运出去了，那就不合法。 - 如果这条出边已经被别的数字沿相同方向走过了一次，那就不合法。 - 如果加上这个数后，当前确定的搬运情况形成了一条**有始有终的**偏序链（也就是上图中，我们已经形成了 $1-2-3-4-5$ 这条链），并且 $u$ 还有别的出边不在这条链上，那就不合法。（因为我们需要把所有出边串到一起） - 否则，一定合法。 对于 $v$ ，可以对称来看： - 如果已经有一个数搬运到它，那就不合法。 - 如果这条出边已经被别的数字沿相同方向走过了一次，那就不合法。 - 如果加上这个数后，当前确定的搬运情况形成了一条**有始有终的**偏序链，并且 $v$ 还有别的出边不在这条链上，那就不合法。 - 否则，一定合法。 对于 $u$ 到 $v$ 的路径上的其它点（记为 $x$ ）： - 如果入边或者出边其中一条已经被别的数字沿相同方向走了一次，那就不合法。 - 如果加上这个数字后，所有**经过** $x$ 的数字连成了一个环，那就不合法。 - 如果加上这个数后，当前确定的搬运情况形成了一条**有始有终的**偏序链，并且 $x$ 还有别的出边不在这条链上，那就不合法。 - 否则，一定合法。 为了判定是否形成了一条偏序链，我们可以对每一个点的所有出边开一个双向链表，记录每一个点当前所在偏序链的开头和结尾，这样所有的操作都可以 $O(1)$ 实现。 直接贪心是 $n^3$ 的，但是我们可以直接以 $u$ 为根对整棵树进行一次 dfs ，然后求出所有合法的 $v$ 中节点编号最小的作为这一轮贪心的答案。 时间复杂度 $O(n^2)$ 。 这道题我大概拿出来了 $2$ 个多小时的时间，中间思路错了几次，最后才形成上面那个成熟的思路。由于时间不够只调过了小样例，大样例死循环了，估计再多给我一段时间的话 Day1 就能 AK 了？（其实 Day2 也是最后十几分钟猜出了 T2 结论没写， ~~所以给我 5 个小时大概能口胡 AK CSP？~~ 然而这和我今年撑死过不了500又有什么关系呢） 考后调好的代码如下： ```cpp #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 掉了……不过貌似能过掉链的数据？