Rt，这不算 tlqtj 吧，毕竟发成题解说缺证明不给过。类似 wmrqwq 的乱搞，直接 dfs，对每个结点 $u$ 贪心去填，保证 $a_u>a_{\operatorname{fa}(u)}$，具体方式为：找到 $>a_{\operatorname{fa}(u)}$ 的最小的没有用过的数字 $p$ 满足 $p-a_{\operatorname{fa}(u)}$ 不为质数，直接令 $a_u\gets p$。

找 $p$ 的实现上，集合 $S$ 存没用过的数字集合，一开始想的是直接拿 $a_{\operatorname{fa}(u)}$ 去 upper_bound，然后在 $S$ 里暴力往后跳到第一个使得差不为质数的 $p$。这样时间复杂度假，被菊花卡。然后加上一个类似当前弧优化的东西，dfs 的过程中把最近填的 $a_u$ 记到 $c_{\operatorname{fa}(u)}$ 上（$c_u$ 即 $u$ 的儿子里已填部分的 $a_{\max}$），求 $a_u$ 时拿 $c_{\operatorname{fa}(u)}$ 去 upper_bound 即可，然后就 AC 了，非常神秘。一个优化是将 dfs 的根设为整棵树的重心，效率能提升一倍。

#include <cstdio>
#include <vector>
#include <set>
 
using namespace std;
 
const int N=414514;
 
bool vis[N]={0,1};int pr[N/5],pc;
 
void sev(){
	for(int i=2;i<N;++i){
		if(!vis[i]) pr[++pc]=i;
		for(int j=1;j<=pc&&i*pr[j]<N;++j){
			vis[i*pr[j]]=1;if(i%pr[j]==0) break;
		}
	}
}
 
vector<int> vc[N];
 
int a[N],cur[N];set<int> S;
 
void dfs(int u,int l){
	auto p=S.upper_bound(cur[l]);
	while(!vis[*p-a[l]]) ++p;
	a[u]=cur[u]=cur[l]=*p;S.erase(p);
	for(int v:vc[u]) if(v!=l) dfs(v,u);
}
 
int main()
{
	sev();int T;scanf("%d",&T);while(T--){
		int n,x,y;scanf("%d",&n);for(int i=1;i<=n<<1;++i) S.insert(i);
		for(int i=1;i<n;++i) scanf("%d%d",&x,&y),vc[x].push_back(y),vc[y].push_back(x);
		dfs(1,0);for(int i=1;i<=n;++i) printf("%d ",a[i]);
		puts("");cur[0]=0;for(int i=1;i<=n;++i) vc[i].clear();
	}
}