自动搬运

查看原文

来自洛谷，原作者为

	Autumn_Rain 机惨我的人妈炸了

搬运于2025-08-24 23:02:32，当前版本为作者最后更新于2024-08-24 22:29:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

• 以 $1$ 为根搜索一遍，把深度为奇数的放入集合 $A$，偶数的放入集合 $B$。

• 发现当 $x,y$ 之间距离为奇数时，当且仅当 $x\in A,y\in B$ 或者 $x\in B,y\in A$。

• 因此给两个集合排个序再轮流取数。发现无法轮流取的时候就输出 $-1$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
//建树 
int T,n,u,v,h[N],d[N],cnt;
struct node{int nxt,to;}e[N];
void add(int u,int v){ 
    e[++cnt].nxt=h[u];
    e[cnt].to=v;
    h[u]=cnt;
}
//遍历整棵树 
void dfs(int u,int fa){
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		d[v]=d[u]+1;//d代表节点深度 
		dfs(v,u);
	}
} 
//两个集合，小根堆维护 
priority_queue<int,vector<int>,greater<int> >S1;
priority_queue<int,vector<int>,greater<int> >S2;
void out1(){//先取第一个集合 
	for(int i=1;i<=n;i++){
		if(i&1){cout<<S1.top()<<" ";S1.pop();continue;}
		else{cout<<S2.top()<<" ";S2.pop();continue;}
	} 
	cout<<"\n";return;
}
void out2(){//先取第二个集合 
	for(int i=1;i<=n;i++){
		if(i&1){cout<<S2.top()<<" ";S2.pop();continue;}
		else{cout<<S1.top()<<" ";S1.pop();continue;}
	} 
	cout<<"\n";return;
}
void clear(){//清空队列 
	while(!S1.empty())S1.pop();
	while(!S2.empty())S2.pop();
}
int main(){
	cin>>T;
	while(T--){
		cin>>n;cnt=0;//清空 
		memset(e,0,sizeof(e));
		memset(h,0,sizeof(h));
		memset(d,0,sizeof(d));
		clear();
		//输入建树 
		for(int i=1;i<n;i++){cin>>u>>v;add(u,v);add(v,u);}
		d[1]=0;dfs(1,0);
		//如果深度奇数放入S1,否则S2 
		for(int i=1;i<=n;i++){
			if(d[i]&1)S1.push(i);//x&1==1代表x是奇数，否则偶数 
			else S2.push(i);
		}
		//两个集合大小 
		int cnt1=S1.size(),cnt2=S2.size();
		if(n&1){//n奇数，无法使两个集合一样多 
			if(max(cnt1,cnt2)-min(cnt1,cnt2)!=1){cout<<"-1\n";continue;}
			//模拟一下发现，cnt1和cnt2只能相差1，不然不可能轮流取
			//且必须先从多的那个集合开始取	
			if(cnt1>cnt2){out1();continue;}
			else{out2();continue;}	
			continue;
		}
		//否则n为偶数时 
		if(cnt1!=cnt2){cout<<"-1\n";continue;}//不相等就无法轮流取 
		out2();continue;//因为d[1]=0，且1是字典序最小的节点，所以从集合2开始输出 
	}
	return 0;
}