CF992Div2 D-solution

给定一个 $n$ 个节点的树，你可以不重复地给树的节点填 $1\sim 2n$ 之间的数，求一种构造方案，使得每两个相邻的节点上的数之差的绝对值为合数。

1. 如果 $siz_{v_0}\neq 1$。
   显然 $x-val_u=siz_{v_0}\times 2$ 是一个合数，我们直接填 $val_{v_1}=x$。则填完后还能从 $x'=val_{v_1}+siz_{v_1}\times 2-1 =val_u+(siz_{v_0}+siz_{v_1})\times 2-1$ 填下一个子树，我们填 $val_{v_2}=x'+1$ 即可满足合数条件。执行这样的操作，我们可以保证填完所有子树后，还能填的数是 $val_u+\sum siz_v\times 2-1<val_u+siz_u\times 2-1$，成立。
2. 如果 $siz_{v_0}=1$。
   • 如果 $siz_u=2$，即 $u$ 只有这一个子树，显然 $val_u+1<val_u+siz_u\times 2-1$。
   • 否则填 $val_{v_1}=val_u+4$，那么接下来能填的数 $x'=val_u+4+siz_{v_1}\times 2-1=val_u+(siz_{v_0}+siz_{v_1})\times 2+1$，于是我们填 $val_{v_2}=x’+1$ 即可满足合数条件。执行这样的操作，我们可以保证填完所有子树后，还能填的数是 $val_{u}+\sum siz_v \times 2+1=val_u+siz_u\times 2-1$，成立。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int>ttfa;
typedef long long ll;

const int N=200005;
int Test;
int n,tot=0,ans[N];

vector<int>tar[N];

void dfs(int u,int f){
	bool flag=0;
	ans[u]=++tot;
	for(auto v:tar[u]){
		if(v==f)continue;
		if(!flag){
			dfs(v,u);
			flag=1;
			continue;
		}
		if(tot+1-ans[u]==2)tot=ans[u]+3;
		else if((tot+1-ans[u])%2==1)++tot;
		dfs(v,u);
	}
}

int main(){
	scanf("%d",&Test);
	while(Test--){
		scanf("%d",&n);tot=0;
		for(int i=1;i<=n;++i)
			tar[i].clear();
		for(int i=1;i<n;++i){
			int u,v;scanf("%d%d",&u,&v);
			tar[u].push_back(v);
			tar[v].push_back(u);
		}
		dfs(1,0);
		for(int i=1;i<=n;++i)
			printf("%d ",ans[i]);
		puts("");
	}
	return 0;
}