题解：CF2112D Reachability and Tree

看起来就在觉得它和 NOI2024 的树的定向（其实我压根儿都没有做过这题）有啥关联，其实一点没有，这是个我上了高一都不会的普及组题。

运用 NOI2024 树的定向特殊性质 A 的思路，对树点黑白染色。每一条边都是指向黑点。就构造出

n-1

的情况了。

设想答案为

n

的情况是把两个距离为

2

的点连接起来。考虑翻转以某一个度数为

2

的节点为根的子树就能达成条件了，否则无解。

要合理选择搜索的根。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	} 
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
} 
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
int n;
vector<int> g[5*114514];
int col[5*114514];
int fa[5*114514];
int col1[5*114514];

struct node{
	int x,y;
}edge[5*114514];
int idx;
void dfs(int u){
	if(u==idx)	col1[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(fa[u]==v)	continue;
		fa[v]=u;
		col[v]=3-col[u];
		if(col1[u])	col1[v]=1;
		dfs(v);
		if(col1[u]&&col1[v]){
			if(col[u]==1)	write1(u);
			else	write1(v);
			if(col[u]==2)	write2(u);
			else	write2(v);
		}
		else{
			if(col[u]==1)	write1(v);
			else	write1(u);
			if(col[u]==2)	write2(v);
			else	write2(u);
		}
	}
}
void solve(){
//	int n=read();
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		edge[i]=(node){u,v};
		g[u].push_back(v),g[v].push_back(u);
	}
	int now=-1;
	for(int i=1;i<=n;i++){
		if(g[i].size()==2)	now=i;
//		cout<<'!'<<i<<' '<<g[i].size()<<endl;
		col[i]=0;
	}
	if(now==-1){
		puts("No");
		for(int i=1;i<=n;i++){
			g[i].clear(),col[i]=fa[i]=col1[i]=0;
		}
		return;
	}
	puts("Yes"); 
	idx=now;
	int u=1;
	if(now==1)	u=2;	//确定根  
	col[u]=1,dfs(u);
//	return;
	for(int i=1;i<=n;i++){
		g[i].clear(),col[i]=fa[i]=col1[i]=0;
	}
	return;
} 
signed main(){
	int T=read();
	while(T--)	solve();
	return 0;
}//一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！

题解：CF2112D Reachability and Tree

文章操作

相关推荐

评论

题解：CF2112D Reachability and Tree