1 条题解

  • 0
    @ 2025-8-24 22:13:04

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Mihari
    您也是这样吧，因为战斗到底——因为努力求生，现在，才能站在这里。

    搬运于2025-08-24 22:13:04，当前版本为作者最后更新于2019-11-21 20:39:40，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    Day1 T3 树上的数

    题目

    点这里

    考场经历+思考

    这道题的输入感觉很恶心。 大概思路就是用 O(n!×n)O(n!\times n) 的复杂度，全排列删边顺序，再用 nn 来计算。 处理了输入很久，但是还是没有调出来。 然后，花费了差不多 1h1h 但是还是没有什么结果。 但是却把 T2T2 的 100pts100pts 全部丢掉了... 代码就不贴了。

    正解

    PS:PS:老师目前并未讲正解，但是部分分讲完了。

    方法 1 : 10pts

    这 10pts10pts 是这一次考试 T3T3 的满分了...

    很少有超过 10pts10pts 的人。

    思路很好想，用一个 dfsdfs 枚举删边的顺序，再用 O(N)O(N) 来检查即可。

    代码见下：（个人代码风格严重）

    /*
	10pts code
*/
#include<cstdio>
#include<utility>
using namespace std;
 
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
//#define FILEOI
 
typedef pair<int,int> pii;
 
#define cg (c=getchar())
template<class T>inline void qread(T& x){
    char c;bool f=0;
    while(cg<'0'||'9'<c)if(c=='-')f=1;
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    if(f)x=-x;
}
inline int qread(){
    int x=0;char c;bool f=0;
    while(cg<'0'||'9'<c)if(c=='-')f=-1;
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
    inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
    if(x<0)return (void)(putchar('-'),fwrit(-x));
    if(x>9)fwrit(x/10);putchar(x%10^48);
}
 
const int MAXN=2000;
 
struct edge{
    int to,nxt;
    edge(){}
    edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,in[MAXN+5],maxin,tcnt;
pii t[MAXN+5];
inline void add_edge(const int u,const int v){
    ++in[u],++in[v];//更改点的入度
    e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
    e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
 
    maxin=Max(maxin,Max(in[u],in[v]));//特判菊花图
    t[++tcnt]=mp(u,v);//记录一条边连接的两个点
}
 
int N,a[MAXN+5],ans[MAXN+5];
//a[i] : 点 i 的数字是多少
//ans[i] : 记录答案
 
inline void init(){
    qread(N);
 
    //清空图
    ecnt=0,tcnt=0,maxin=0;
    rep(i,1,N)tail[i]=0,in[i]=0,ans[i]=N-i+1;
 
    //输入
    rep(i,1,N)a[qread()]=i;
    rep(i,1,N-1)add_edge(qread(),qread());
}
 
bool vis[MAXN+5];int mir[MAXN+5];
void dfs(const int);
inline void getDfs(){
    dfs(1);
    rep(i,1,N)writc(ans[i],' ');
    putchar('\n');
}
inline void chk(){
    rep(i,1,N)mir[a[i]]=i;
    rep(i,1,N){
        if(mir[i]<ans[i]){
            rep(j,1,N)ans[j]=mir[j];
            break;
        }
        if(mir[i]>ans[i])break;
    }
    return;
}
void dfs(const int p){
    if(p==N)return chk();
    rep(i,1,N-1)if(!vis[i]){
        swap(a[t[i].ft],a[t[i].sd]);vis[i]=true;
        dfs(p+1);
        swap(a[t[i].ft],a[t[i].sd]);vis[i]=false;
    }
}
 
int T;
 
signed main(){
#ifdef FILEOI
    freopen("file.in","r",stdin);
    freopen("file.out","w",stdout);
#endif
    qread(T);
    while(T--){
        init();
        if(N<=10) getDfs();//暴力
        else puts("gugugu~~~");//减少测试时间
    }
    return 0;
}

    方法 2 : 35pts

    在拿到暴力的 10pts10pts 之后，我们应该朝着更高的得分奋斗。

    那么接下来，我们看到链和菊花图。

    哪个更好想？

    各位即将进入省队的大佬们，你们应该思考过吧。

    下一个部分分，应该拿下菊花图。

    怎么做？ 这是一个好问题

    不妨看一看菊花图有什么特性。

    假如说我们有这样一个菊花图：

    graph.png

    我们考虑随便删一些边。

    假如我们删除边 {1,4}\{1,4\} ，那么 P4−>Y7P_4->Y_7 是一定可以保证的，因为除了这一条边 {1,4}\{1,4\} 以外，没有边和 44 号点有关。

    再随便来，把边 {1,2}\{1,2\} 删掉，那么 P2−>Y1P_2->Y_1 也是一定保证了，理由同上。

    再试几次，发现在菊花图上，除了花心以外，其他点一定固定了是删边时花心的值，而它本身的数跑到花心，作为下一次固定的值。

    仔细想想，是不是有点像一个环，或者说是一条单链？

    为什么这么说？

    我们这样看，删 {1,4}\{1,4\} ，等于加边 {Y7−>P4}\{Y_7->P_4\} ，此时 P1−>Y1P_1->Y_1 。

    再删边 {1,2}\{1,2\} ，等于加边 Y1−>P2{Y_1->P_2} ，此时 P1−>Y3P_1->Y_3 .

    再枚举几次，发现每个数字 YiY_i 只会最多向外连出一条边。

    这相当于是一条单链，但是最后连 YnY_n 时，整个图一定会连成一个大环。

    但是在连边的时候，我们要注意提前成环的情况——用并查集解决这个问题。

    代码见下：

    #include<cstdio>
#include<utility>
using namespace std;
 
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
//#define FILEOI
 
typedef pair<int,int> pii;
 
#define cg (c=getchar())
template<class T>inline void qread(T& x){
    char c;bool f=0;
    while(cg<'0'||'9'<c)if(c=='-')f=1;
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    if(f)x=-x;
}
inline int qread(){
    int x=0;char c;bool f=0;
    while(cg<'0'||'9'<c)if(c=='-')f=-1;
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
    inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
    if(x<0)return (void)(putchar('-'),fwrit(-x));
    if(x>9)fwrit(x/10);putchar(x%10^48);
}
 
const int MAXN=2000;
 
struct edge{
    int to,nxt;
    edge(){}
    edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,in[MAXN+5],maxin,tcnt;
pii t[MAXN+5];
inline void add_edge(const int u,const int v){
    ++in[u],++in[v];//更改点的入度
    e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
    e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
 
    maxin=Max(maxin,Max(in[u],in[v]));//特判菊花图
    t[++tcnt]=mp(u,v);//记录一条边连接的两个点
}
 
int N,a[MAXN+5],ans[MAXN+5];
//a[i] : 点 i 的数字是多少
//ans[i] : 记录答案
 
inline void init(){
    qread(N);
 
    //清空图
    ecnt=0,tcnt=0,maxin=0;
    rep(i,1,N)tail[i]=0,in[i]=0,ans[i]=N-i+1;
 
    //输入
    rep(i,1,N)a[qread()]=i;
    rep(i,1,N-1)add_edge(qread(),qread());
    /*
    rep(i,1,N)writc(a[i],' ');
    putchar('\n');
    */
}
 
int pre[MAXN+5];
inline void buildSet(){rep(i,1,N)pre[i]=i;}
int findSet(const int u){return u==pre[u]?u:pre[u]=findSet(pre[u]);}
inline void unionSet(const int u,const int v){return (void)(pre[findSet(u)]=findSet(v));}
 
bool vis[MAXN+5];
int tmp[MAXN+5],pt[MAXN+5];
 
inline void work(){//处理菊花图
    buildSet();
    rep(i,1,N)tmp[a[i]]=i,vis[i]=0;
    rep(i,1,N-1){
        rep(j,1,N)if(!vis[j]&&findSet(tmp[i])!=findSet(j)){
            vis[j]=true,pt[tmp[i]]=j;
            unionSet(tmp[i],j);
            break;
        }
    }
    rep(i,1,N-1)writc(pt[tmp[i]],' ');
    rep(i,1,N)if(!vis[i]){
        writc(i,'\n');
        break;
    }
}
 
int mir[MAXN+5];
void dfs(const int);
inline void getDfs(){
    rep(i,1,N)vis[i]=0;
    dfs(1);
    rep(i,1,N-1)writc(ans[i],' ');
    writc(ans[N],'\n');
}
inline void chk(){
    rep(i,1,N)mir[a[i]]=i;
    rep(i,1,N){
        if(mir[i]<ans[i]){
            rep(j,1,N)ans[j]=mir[j];
            break;
        }
        if(mir[i]>ans[i])break;
    }
    return;
}
void dfs(const int p){
    if(p==N)return chk();
    rep(i,1,N-1)if(!vis[i]){
        swap(a[t[i].ft],a[t[i].sd]);vis[i]=true;
        dfs(p+1);
        swap(a[t[i].ft],a[t[i].sd]);vis[i]=false;
    }
}
 
int T;
 
signed main(){
#ifdef FILEOI
    freopen("file.in","r",stdin);
    freopen("file.out","w",stdout);
#endif
    qread(T);
    while(T--){
        init();
        if(N<=10)getDfs();
        else if(maxin==N-1)work();
        else puts("gugugu~~~");
    }
    return 0;
}

    方法 3 : 60pts

    在得到 45pts45pts 之后，你一定很开心，但是如果这是考试，那是一定不够的。

    但是如果这是考试，那是一定不够的。

    我们继续朝更高的得分奋斗，那么我们现在开始分析链。

    首先，链有什么特性？似乎这是很简单的一个问题。

    它的特性显然：

    • 它是一条类似于线的东西；
    • 除了两个端点之外，其他的点度都为 22（分出度和入度）；
    • ...（作者太弱，只想得出这几种情况）

    那么，针对这些情况进行分析：

    针对特性1，我们为了方便处理，可以把这个单链拍到树上，代码如下：

    int lt[MAXN+5],lcnt;//链表和下标
inline void getlist(const int u,const int pre){
	lt[pt[u]=++lcnt]=u;//pt[i] : 点 i 在链表数组中的位置
	for(int i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=pre)
		getlist(v,u);
}

    这个地方很简单。

    那么特性2？

    所谓入度、出度为 22 即除端点以外，每个点都有两条边与其相连，而这两条边可以保证的是删除时间一定不同。

    那么，我们可以对于这两条边进行标记，分几种情况：

    • 左边的边先删，右边的边后删（左先右后）
    • 左后右先
    • 没有过标记

    针对这个，我们用一个数组来存

    short int mark[MAXN+5];//标记 : 0-无标记 ; 1-左先右后 ; 2-左后右先

    此处选用 short int 为的是节省内存 其实省不了多少

    为什么这样标记呢？我们来分析一种情况。

    假设数 xx 要到点 ii 去，如下图：

    graph _1_.png

    边上的数字是边的编号。

    重复一遍问题：数字 xx 要去 ii 点

    那么首先，edge1edge_1 一定是在 edge2edge_2 之后删，不然数字 xx 就跑到其他地方去了。

    根据 mark[]mark[] 数组的定义，可得 mark[x]=2mark[x]=2

    同理，edge2、edge3、edge4、edge5edge_2、edge_3、edge_4、edge_5 一定是依次删除的，那么可得 mark[p1]=mark[p2]=mark[p3]=1mark[p1]=mark[p2]=mark[p3]=1

    而点 ii ，要保证的是 edge6edge_6 在 edge5edge_5 之前删除，为什么？

    因为当 xx 到 ii 点之后，如果 edge6edge_6 还存在，那么 xx 就会跑到 p4p_4 那里去。

    由此推出，mark[i]=2mark[i]=2

    这是 xx 往右走的情况，xx 往左的情况可自行推导 要看代码我也不拦你，推荐自己推一下，很简单

    而最后，我们判定一个方法是否可行，只需要判断它和前面的边的标记是否冲突即可。

    #include<cstdio>
#include<utility>
using namespace std;

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
// #define FILEOI

typedef pair<int,int> pii;

#define cg (c=getchar())
template<class T>inline void qread(T& x){
	char c;bool f=0;
	while(cg<'0'||'9'<c)if(c=='-')f=1;
	for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
	if(f)x=-x;
}
inline int qread(){
	int x=0;char c;bool f=0;
	while(cg<'0'||'9'<c)if(c=='-')f=-1;
	for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
	return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
	inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
	if(x<0)return (void)(putchar('-'),fwrit(-x));
	if(x>9)fwrit(x/10);putchar(x%10^48);
}

const int MAXN=2000;

struct edge{
	int to,nxt;
	edge(){}
	edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,in[MAXN+5],maxin,tcnt;
pii t[MAXN+5];
inline void add_edge(const int u,const int v){
	++in[u],++in[v];//更改点的入度
	e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
	e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;

	maxin=Max(maxin,Max(in[u],in[v]));//特判菊花图
	t[++tcnt]=mp(u,v);//记录一条边连接的两个点
}

int N,a[MAXN+5],ans[MAXN+5];
//a[i] : 点 i 的数字是多少
//ans[i] : 记录答案

inline void init(){
	qread(N);

	//清空图
	ecnt=0,tcnt=0,maxin=0;
	rep(i,1,N)tail[i]=0,in[i]=0,ans[i]=N-i+1;

	//输入
	rep(i,1,N)a[qread()]=i;
	rep(i,1,N-1)add_edge(qread(),qread());
	/*
	rep(i,1,N)writc(a[i],' ');
	putchar('\n');
	*/
}

int pre[MAXN+5];
inline void buildSet(){rep(i,1,N)pre[i]=i;}
int findSet(const int u){return u==pre[u]?u:pre[u]=findSet(pre[u]);}
inline void unionSet(const int u,const int v){return (void)(pre[findSet(u)]=findSet(v));}

bool vis[MAXN+5];
int tmp[MAXN+5],pt[MAXN+5];

inline void work(){//处理菊花图
	buildSet();
	rep(i,1,N)tmp[a[i]]=i,vis[i]=0;
	rep(i,1,N-1){
		rep(j,1,N)if(!vis[j]&&findSet(tmp[i])!=findSet(j)){
			vis[j]=true,pt[tmp[i]]=j;
			unionSet(tmp[i],j);
			break;
		}
	}
	rep(i,1,N-1)writc(pt[tmp[i]],' ');
	rep(i,1,N)if(!vis[i]){
		writc(i,'\n');
		break;
	}
}

int mir[MAXN+5];
void dfs(const int);
inline void getDfs(){
	rep(i,1,N)vis[i]=0;
	dfs(1);
	rep(i,1,N-1)writc(ans[i],' ');
	writc(ans[N],'\n');
}
inline void chk(){
	rep(i,1,N)mir[a[i]]=i;
	rep(i,1,N){
		if(mir[i]<ans[i]){
			rep(j,1,N)ans[j]=mir[j];
			break;
		}
		if(mir[i]>ans[i])break;
	}
	return;
}
void dfs(const int p){
	if(p==N)return chk();
	rep(i,1,N-1)if(!vis[i]){
		swap(a[t[i].ft],a[t[i].sd]);vis[i]=true;
		dfs(p+1);
		swap(a[t[i].ft],a[t[i].sd]);vis[i]=false;
	}
}

int lt[MAXN+5],lcnt;
short int mark[MAXN+5];//标记 : 0-无标记 ; 1-左先右后 ; 2-左后右先
inline void getlist(const int u,const int pre){
	lt[pt[u]=++lcnt]=u;
	for(int i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=pre)
		getlist(v,u);
}
inline bool chkl(const int p1,const int p2){
	if(mark[pt[p1]]==1)return false;

	rep(i,pt[p1]+1,pt[p2]-1)if(mark[i]==2)return false;

	if(mark[pt[p2]]==1)return false;

	return true;
}
inline void getMarkl(const int p1,const int p2){//当 pt[p1]<=pt[p2] 时
	if(pt[p1]!=1&&pt[p1]!=N)mark[pt[p1]]=2;

	rep(i,pt[p1]+1,pt[p2]-1)mark[i]=1;

	if(pt[p2]!=1&&pt[p2]!=N)mark[pt[p2]]=2;
}
inline bool chkr(const int p1,const int p2){//当 pt[p1]>pt[p2] 时
	if(mark[pt[p1]]==2)return false;

	fep(i,pt[p1]-1,pt[p2]+1)if(mark[i]==1)return false;

	if(mark[pt[p2]]==2)return false;

	return true;
}
inline void getMarkr(const int p1,const int p2){
	if(pt[p1]!=1&&pt[p1]!=N)mark[pt[p1]]=1;

	fep(i,pt[p1]-1,pt[p2]+1)mark[i]=2;

	if(pt[p2]!=1&&pt[p2]!=N)mark[pt[p2]]=1;
}
inline void workList(){//解决单链
	lcnt=0;
	rep(i,1,N)if(in[i]==1){//压到数组上面
		getlist(i,0);
		break;
	}
	/*
	printf("this is the list:");
	rep(i,1,N)writc(lt[i],' ');
	putchar('\n');
	printf("this is pt arr:");
	rep(i,1,N)writc(pt[i],' ');
	putchar('\n');
	*/

	rep(i,1,N)vis[i]=false,mir[a[i]]=i,mark[i]=0;

	rep(i,1,N)rep(j,1,N)if(!vis[j]&&pt[j]!=pt[mir[i]]){
		//目标位置不能和本来的位置重合并且目标位置还没有被其他优先级更高的数占有
		// printf("Now the number is %d, the goal position is %d\n",i,j);
		int p1=mir[i],p2=j;bool flg=false;
		if(pt[p1]<=pt[p2]){//如果这个数是往左边走
			if(chkl(p1,p2))
				getMarkl(p1,p2),flg=true;
		}
		else{//反之
			if(chkr(p1,p2))
				getMarkr(p1,p2),flg=true;
		}
		if(flg){//记录答案
			ans[i]=j,vis[j]=true;
			break;
		}
	}
	rep(i,1,N-1)writc(ans[i],' ');//输出答案
	writc(ans[N],'\n');
}

int T;

signed main(){
#ifdef FILEOI
	freopen("rdata.out","r",stdin);
	freopen("file.out","w",stdout);
#endif
	qread(T);
	while(T--){
		init();
		if(N<=10)getDfs();
		else if(maxin==N-1)work();
		else if(maxin==2)workList();
		else puts("gugugu~~~");
	}
	return 0;
}

    方法 4 : 100pts

    目前尚待讨论...

    ljlj 大佬憋了两天，终于舍得把正解讲出来了，接下来是正解：

    首先，我们的单链是怎么做的？

    维护一个点的两个边删除的先后顺序。

    并且，我们可以得到这样一个结论： 一个比较容易想到的结论

    只有共用同一个顶点的边才有删除的先后关系

    而判定一个方法是否可行，只需看这个方案是否和前面的方案冲突即可。

    那么，我们能否将这样的维护扩展到多条边的情况？其实是可以的 不然我为什么要问这个问题

    只有两条边，我们只需维护 左前右后 或者 左后右前 的情况，但是对于多条边这样显然是不行的。

    那么，对于多个删边的先后关系，我们将其排成一排，比如我们删边顺序是：1,3,5,4...1,3,5,4...

    将它们排成一排之后，发现它有点像链表。

    考虑用链表维护删除边的先后关系。

    但是这里有个问题：如果一个点删除边的顺序不一定是连续的怎么办？

    对于这种情况，我们只需要把它们看成有许多个链表，但是它们没有接在一起即可。

    那么，我们怎么寻找一条合法路径？

    我们把这个方法的寻径算法分成几个部分：

    • 对于起飞点（即数字一开始所在的点）
    • 对于中转点
    • 对于结束点

    部分 1:对于起飞点

    对于一个起飞点 uu，我们考虑寻找一条起飞边，并且这条起飞边是一定存在。

    那么，这条起飞边需要满足什么条件？

    首先，这条起飞边前面不能有什么其他的东西。

    即对于点 uu 的删边顺序所连成的链表集中，这条边必须是其中某一条链的起点。

    而且，我们分析，如果这是一条起飞边，那么它一定是所有 uu 的边中最先删除的那条边（如果不知道为什么，参考本题链的处理方法）

    还有一种特殊情况，留到后面结束点之后分析。

    部分 2:对于中转点

    如果这是一个中转点，考虑枚举一条边 e′e' 在 ee (我们之前删除的那条边)

    而这个中转点必须满足什么条件呢?

    毕竟 e′e' 是接在 ee 之后的，那么一定要保证 e′e' 之前没有其他的边。

    而且，点 e′e' 与点 ee 还没有连在一起，即它们分别所在不同的链上（因为我们本来就是要将他们连在一起）。

    并且，e′e' 是在 ee 之后，但是如果 e′e' 是一条起飞边，即这条边必须是最先删除的，那么 e′e' 就是不符合的。

    还有一种特殊情况，留到后面结束点之后分析。

    部分 3:对于降落点

    如果点 uu 是一个降落点，那么我们的边 ee 必须是最后删除的（如果不知道为什么，参考本题链的处理方式）

    即，对于一个点 uu ，我们目前还并未指定 uu 的某一条边必须是结束边。

    但是还有一种情况，这种情况与前面的两个部分都有关。

    如果这条结束边 ee 是与前面的起飞边在同一条链上，即它们先后顺序已确定，那么我们必须要保证这个删边顺序组成的链中，长度刚好为 uu 的边数。

    为什么？因为我们最后，必须保证每条边都被删去。

    而上面这种情况，即是我们将最开头所删除的边，与最末尾所删除的边连接在一起而形成一个完整的、已无法再次修改的长链，而如果有剩余的边没有被删去，它们就没有机会再插入到这个链之中，也就是说找不到任何一个机会去删除这条边，与题意不符。

    生动地说，我们不能让这个完整的链出现提前自闭的情况。

    知道这个之后，我们再反过来补充 部分 1 与 部分 2 。

    部分 1 补充

    因为我们已经指定起飞边 ee ，而我们要将边 e′e' 接到 ee 之后。

    但是如果 e′e' 已经与降落边，即末删边相连，那么我们也要防止提前自闭的情况。

    所以我们也要特判一下，链长度必须与 uu 的边数一样。

    部分 2 补充

    如果我们的边 ee 已经连接到起始边，而 e′e' 已经连接到末删边。

    那如果我们要将 ee 与 e′e' 连起来删，也就是将两个完整链连接起来，这也是防止提前自闭的情况。

    总的时间复杂度 O(N2)O(N^2) ，常数我就不知道了，但是能过...

    代码如下（自带注释）

    #include<cstdio>
#include<vector>
using namespace std;

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
// #define FILEOI

#define cg (c=getchar())
template<class T>inline void qread(T& x){
	char c;bool f=0;
	while(cg<'0'||'9'<c)if(c=='-')f=1;
	for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
	if(f)x=-x;
}
inline int qread(){
	int x=0;char c;bool f=0;
	while(cg<'0'||'9'<c)if(c=='-')f=-1;
	for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
	return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
	inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
	if(x<0)return (void)(putchar('-'),fwrit(-x));
	if(x>9)fwrit(x/10);putchar(x%10^48);
}

const int MAXN=2000;

struct edge{
	int to,nxt;
	edge(){}
	edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,siz[MAXN+5];
inline void add_edge(const int u,const int v){
	++siz[u],++siz[v];
	e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
	e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
}

int N,minp;
int pt[MAXN+5];
int pre[MAXN+5][MAXN+5],nxt[MAXN+5][MAXN+5];
//这条边的 前驱,后继
int rt[MAXN+5][MAXN+5][2];
//点 u 的某一条边的 前根节点、后根节点
int len[MAXN+5][MAXN+5];
//这条边 所在链 的链表长度

inline void init(){
	qread(N);
	ecnt=0;
	rep(i,1,N)qread(pt[i]),tail[i]=siz[i]=0;
	rep(i,1,N+1)rep(j,1,N+1)len[i][j]=pre[i][j]=nxt[i][j]=rt[i][j][0]=rt[i][j][1]=0;

	int u,v;
	rep(i,1,N-1){
		qread(u,v);
		add_edge(u,v);
		pre[u][v]=pre[v][u]=nxt[u][v]=nxt[v][u]=0;
		rt[u][v][0]=rt[u][v][1]=v;
		rt[v][u][0]=rt[v][u][1]=u;
		len[u][v]=len[v][u]=1;
	}
}

void findPath(const int u,const int p){//当前节点、前一个节点
	int a=rt[u][p][0],b=rt[u][p][1],ta,tb;
	//a:来的边的前根 ; b:来的边的后根
	if(p==N+1){//这是起点
		for(int i=tail[u],v;i;i=e[i].nxt){//从哪条边起飞
			v=e[i].to;
			ta=rt[u][v][0],tb=rt[u][v][1];
			if(ta!=v || (pre[u][p]==tb && len[u][ta]<siz[u]))
			//条件一:如果这条边已经有一个起点且不是自己
			//条件二:如果后面的那条边已经连接尾端, 且这条链的长度无法满足将所有边连起来
				continue;//那么就不能把 边{u,p} 与 边{u,v} 连在一起
			findPath(v,u);//否则可行
		}
	}
	else{
		if(p==b){//如果 边{u,p} 的后面还暂时没有指定必须删哪一条边, 那么就可以考虑枚举一条边接在后面
			if(pre[u][N+1]==0 && (nxt[u][N+1]!=a || len[u][a]==siz[u]))//则可以考虑在点 u 进行降落, 满足以下条件:
			//如果这个点的末删边还没有被指定(必须满足)
			//并且:
			//1.如果这条链接上开头，那么如果必须满足所有的边都在这条链上
			//2.如果没有接上开头，那么长度随意
				minp=Min(minp,u);//如果满足, 则 u 可以作为一个降落点

			for(int i=tail[u],v;i;i=e[i].nxt){//假定 u 为一个中转点, 则再枚举一条边作为 边{u,p} 的出边，与其尾相连
				v=e[i].to;
				ta=rt[u][v][0],tb=rt[u][v][1];
				if(a==ta || ta!=v || nxt[u][N+1]==v)//第一种大情况
				//如果这两条边已经在同一条链上
				//或者这个边不是一个起始边, 即枚举边的前面还有东西
				//或者枚举边是一条起飞边, 即保证它是所有对于 u 的边必须最先删除的边
					continue;//那么 当前 边{u,p} 都不能接在这条枚举边之上
				
				if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])
				//如果这两条边分别属于这个点 最先删除、最后删除 的链表上的 尾、头
				//那么它们组合起来必须等于所有边的数量之和
				//否则, 这就是 提前自闭 的情况
					continue;

				findPath(v,u);//如果以上都不满足, 那么这条边是合法的
			}
		}
		else findPath(nxt[u][p],u);//否则我们只能按照之前的规定访问这条边
	}
}

inline void merge(const int u,const int a,const int b){
//函数条件:以 a 所在的链表为前链表
//并且满足 a 是前链表尾, b 是后链表头
	int ta=rt[u][a][0],tb=rt[u][b][1];
	nxt[u][a]=b;
	pre[u][b]=a;
	for(int i=ta;i && i!=N+1;i=nxt[u][i]){
	//访问链表的基本操作
		//更新每个点的前根、后根
		rt[u][i][0]=ta;
		rt[u][i][1]=tb;
	}
	len[u][ta]+=len[u][b];
}

bool getMark(const int u,const int p){//还原路径, 并且给路径打上标记
//如果这条路径找到终点, 返回 1, 否则返回 0
	if(u==minp){//如果找到了终点
		pre[u][N+1]=p;//把这条边设为最后删除的边
		nxt[u][p]=N+1;//并且把这条边的下一条边标记为 N+1, 表示这条边是最后删除的
		return 1;
	}
	int a=rt[u][p][0],b=rt[u][p][1],ta,tb;
	if(p==N+1){//这是起飞点
		for(int i=tail[u],v;i;i=e[i].nxt){
			v=e[i].to;
			ta=rt[u][v][0],tb=rt[u][v][1];
			if(ta!=v || (pre[u][N+1]==tb && len[u][ta]<siz[u]))
			//如果枚举边前面有东西, 那么这肯定不能接在起始边的后面, 因为它前面已经有个什么 逼 了
			//或者是枚举边连接到末尾, 但是这条单链长度不够将所有的边包含到链里面
				continue;//那么这条边肯定不在路径上面, 可直接跳过
			if(getMark(v,u)){//如果这就是正确的路径
				nxt[u][N+1]=v;//因为 u 点是起飞点, 所以把这条边记录为 u 的起飞边
				pre[u][v]=N+1;//同时标记这条边的前驱, 与前面的 if 相互呼应(这不是语文...)
				return 1;
			}
		}
	}
	else{//如果点 u 是中转点, 那么考虑枚举中转边
		if(p==b){//如果这条边在链上后面没有其他边的时候
			for(int i=tail[u],v;i;i=e[i].nxt){
				v=e[i].to;
				ta=rt[u][v][0],tb=rt[u][v][1];
				if(a==ta || ta!=v || nxt[u][N+1]==v)//参考 findPath() 中相同位置的注释
					continue;
				if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])//同样参考 findPath() 中同样位置
					continue;
				if(getMark(v,u)){
					merge(u,p,v);//把链表合并为一个
					return 1;
				}
			}
		}
		else getMark(nxt[u][p],u);
	}
	return 0;
}

signed main(){
#ifdef FILEOI
	freopen("rdata.out","r",stdin);
	freopen("file.out","w",stdout);
#endif
	int T=qread();
	while(T--){
		init();
		if(N==1){
			writc(1,'\n');
			continue;
		}
		rep(i,1,N){
			minp=N+1;
			findPath(pt[i],N+1);
			// printf("%d\n",minp);
			getMark(pt[i],N+1);
			writc(minp,' ');
		}
		putchar('\n');
	}
	return 0;
}
    • 1

    [CSP-S2019] 树上的数

    信息

    ID
    4657
    时间
    2000ms
    内存
    250MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 26ms