CSP D1 T3 树上的数
VerakinT
·
·
个人记录
题意简述
有一颗n个节点的树，每个节点上有一个权值
可以通过删一条边来交换两个点上的点权
问最后删掉所有边后，将数字 1 \sim n 所在的结点编号依次排列，就得到一个结点编号的排列 P_i 。
现在请你求出，在最优操作方案下能得到的字典序最小的 P_i
首先对于一个点x，无论是删左边还是右边，都会是类似于下图这种情况的结果
考虑节点度数大于等于2的时候，（如下图所示 ），实际上已经确定了偏序关系，简单概括一下就是对于一个点x，把所有经过他的数字连到一起，刚好把他的所有出边连成一条偏序链
以此方可贪心，现在考虑一个子问题，假设我们需要将x上的数字搬到y上面，我们需要判断 {X}\to_{Y} 这条 路径 是否合法
有这些情况
我们考虑对于 x :
* 如果已经有一个数从他搬出去了，不合法。
* 如果这条出边已经被别的数字沿相同的方向走过了一次，那就不合法
* 如果加上这个数后，当前已经确定的搬运情况形成了一条 有始有终 的偏序链（也就正如上图中，我们已经形成了 1-2-3-4-5 这条链），并且还有别的出边不在这条链上，不合法，因为我们需要把所有的出边串在一起）
* otherwise 一定合法
类似的 我们考虑y
* 如果有一个数搬运到他，不合法
* 如果这条出边已经被别的数字沿相同方向走过了一次，不合法
* 加上这个数后，当前已经确定的搬运状况形成了一条有始有终的偏序链，并且x还有别的出边不在这条链上，不合法
* otherwise 一定合法
对于 x 到 y 的路径上的其他点（记为u）：
* 如果入边或者出边其中一条已经被别的数字沿相同方向走了一次，不合法
* 如果加上这个数后，当前确定的搬运情况形成了一条有始有终的偏序链，并且x还有别的出边不在这条链上，不合法
* otherwise 一定合法
为了判断是否形成了一条偏序链，我们可以对每一个点的所有出边开一个双向链表，记录每一个当前点所在的偏序链的开头和结尾，这样所有的操作都可以O(1)实现
直接以x为根对整棵树进行一次dfs，然后求出所有合法的y中节点编号最小的作为这一轮贪心的答案。
总复杂度 O（n^{2}）
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int Max_N=2020;
int t,n,fath[Max_N],head[Max_N];
int cnt,val[Max_N],edge[Max_N][Max_N];
bool flag[Max_N];
int st[Max_N][Max_N],ed[Max_N][Max_N];
int from[Max_N],too[Max_N];
int d1[Max_N],d2[Max_N],d[Max_N];
//d[i]表示第i个点还有多少条出边没有被走过
//d1[i]表示第i个点还有多少条出边只被一个数字走进来了一次
//d2[i]表示第i个点还有多少条出边只被一个数字走出去了一次
//from[i]表示搬运到第i个点的数字是从哪个方向来的
//too[i]表示第i个点上的数字被搬运到了哪个方向
// st--> i,j所在的偏序链中的开头指向那个节点
// ed--> i,j所在的偏序链中的结尾指向那个节点
struct edge{int to,next,dis;}p[Max_N<<1];
inline void addedge(int x,int y)
{cnt++;p[cnt].to=y;p[cnt].next=head[x];head[x]=cnt;}
inline void dfs_solve(int x,int root) {
for(register int i=head[x];i;i=p[i].next) {
int y=p[i].to;
if( y==fath[x] ) continue;
fath[y]=x;
flag[y]=1;
if( x!=root ) {
if( edge[fath[x]][x]==fath[x] ||
edge[x][y]==x ) flag[y]=0;
if( edge[fath[x]][x]==0 ||
edge[x][y]==0 ) flag[y]=0;
if( ed[x][y]==from[x]
&& st[x][fath[x]]==too[x] &&
d1[x]+d2[x]+d[x]*2-2>0 ) flag[y]=0;
if( ed[x][y]==fath[x] ) flag[y]=0;
}
else {
if( edge[x][y]==x ) flag[y]=0;
if( edge[x][y]==0 ) flag[y]=0;
if( from[x] ) {
if( ed[x][y]==from[x] &&
d[x]+d1[x]+d2[x]-1!=0 ) flag[y]=0;
}
}
flag[y]&=flag[x]; dfs_solve(y,x);
}
if( x==root ) flag[x]=0;
else {
if( from[x] ) flag[x]=0;
if( too[x] ) {
if( ed[x][too[x]]==fath[x] && d[x]+d1[x]+d2[x]-1!=0 )
flag[x]=0;
}
}
}
int main() {
scanf("%d",&t);
while( t-- ) {
scanf("%d",&n);
cnt=0;
memset(head,0,sizeof(head));
memset(from,0,sizeof(from));
memset(too,0,sizeof(too));
memset(d,0,sizeof(d));
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
for(register int i=1;i<=n;i++) {
scanf("%d",&val[i]);
} int x,y;
for(register int i=1;i<n;i++) {
scanf("%d%d",&x,&y);
addedge(x,y); addedge(y,x);
d[x]++; d[y]++;
edge[x][y]=edge[y][x]=-1;
ed[x][y]=st[x][y]=y;
ed[y][x]=st[y][x]=x;
}
for(register int i=1;i<=n;i++) {
flag[val[i]]=1;
for(register int j=1;j<=n;j++) fath[j]=0;
dfs_solve(val[i],val[i]);
int res=0;
for(register int j=1;j<=n;j++) {
if( flag[j] ) {
res=j; break;
}
}
printf("%d ",res);
from[res]=fath[res];
while( fath[res]!=val[i] ) {
if( edge[fath[res]][res]==-1 ) {
edge[fath[res]][res]=edge[res][fath[res]]=fath[res];
d[res]--; d2[res]++;
d[fath[res]]--; d1[fath[res]]++;
}
else {
edge[fath[res]][res]=edge[res][fath[res]]=0;
d1[res]--; d2[fath[res]]--;
}
int t=res;
res=fath[res];
st[res][ed[res][t]]=st[res][fath[res]];
ed[res][st[res][fath[res]]]=ed[res][t];
}
if( edge[fath[res]][res]==-1 ) {
edge[fath[res]][res]=edge[res][fath[res]]=fath[res];
d[res]--; d2[res]++;
d[val[i]]--; d1[val[i]]++;
}else {
edge[fath[res]][res]=edge[res][fath[res]]=0;
d1[res]--; d2[val[i]]--;
}
too[val[i]]=res;
}
puts("");
}
return 0;
}