2024HDU Contest 5 Problem 5

题目链接

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

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

#include<bits/stdc++.h> 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<int> 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<n;i++){ 			cin>>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;i<n;i++){ 			if(dep[eu[i]]>dep[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<n;i++)printf("%d ",ans[i]); 		puts(""); 	} 	exit(0); 	//return 0; }  

每条边只会被合并一次，然后枚举倍数的时间开销也是调和级数，所以总复杂度为$O(n\log n)$。