题目链接

从大到小枚举gcd的值 d d d，以及编号为 d d d的倍数的点， [ d , 2 d , 3 d , …   ] [d,2d,3d,\dots] [d,2d,3d,…]。
然后对于任何一条边 ( x , y ) (x,y) (x,y)，如果 x x x的子树和 y y y的子树里都有编号为 d d d倍数的点，则这条边的答案至少为d。考虑到对于每条边我们只需要知道最大值，所以如果一条边已经在之前的 d d d中被更新过答案，我们就可以将它合并起来。合并的过程可以通过并查集来实现。

所以总结下来做法就是枚举出编号为 d d d的倍数的点之后，将这些点之间的路径都遍历一遍并合并起来。

#include using namespace std; const int maxn=1e6+5; int t,n,f[maxn]; int eu[maxn],ev[maxn]; inline int find(int x){ 	return f[x]==x?f[x]:f[x]=find(f[x]); } vector g[maxn]; int par[maxn],dep[maxn]; void dfs(int u,int fa){ 	par[u]=fa;dep[u]=dep[fa]+1; 	for(auto v:g[u]){ 		if(v==fa)continue; 		dfs(v,u); 	} } int ind[maxn],ans[maxn]; signed main(){ 	int size(256<<20); //256M 	__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size)); 	ios::sync_with_stdio(0); 	cin.tie(0); 	//freopen("5.in","r",stdin); 	//freopen("5.out","w",stdout); 	cin>>t; 	while(t--){ 		cin>>n; 		for(int i=1;i<=n;i++)g[i].clear(); 		for(int i=1;i>eu[i]>>ev[i]; 			g[eu[i]].push_back(ev[i]); 			g[ev[i]].push_back(eu[i]); 		} 		dfs(1,0); 		for(int i=1;idep[ev[i]]){ 				ind[eu[i]]=i; 			} 			else{ 				ind[ev[i]]=i; 			} 		} 		for(int i=1;i<=n;i++)f[i]=i; 		for(int d=n/2;d>=1;d--){ 			int x=find(d); 			for(int j=d+d;j<=n;j+=d){ 				int y=find(j); 				while(x!=y){ 					if(dep[x]>dep[y])swap(x,y); 					ans[ind[y]]=d; 					f[y]=find(par[y]); 					y=find(par[y]); 				} 			} 		} 		for(int i=1;i