2024HDU Contest 5 Problem 5
创始人
2024-11-11 18:07:17
0

题目链接

从大到小枚举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

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

相关内容

热门资讯

规律教程!xpoker辅助助手... 规律教程!xpoker辅助助手德州辅助app官方最新版本介绍下载(果真真的有挂)1、每一步都需要思考...
详细教程!!wpk私人辅助德扑... 详细教程!!wpk私人辅助德扑之星透视软件(一直真的有挂)1、下载好wpk私人辅助辅助软件之后点击打...
教你教程!cloudpoker... 教你教程!cloudpoker外挂WePOKer有没有透视方法(一般真的有挂)1、cloudpoke...
专业教程!wejoker黑侠辅... 专业教程!wejoker黑侠辅助器HHpoker可以开挂吗(一贯真的有挂);进入游戏-大厅左侧-新手...
透牌教程!哈糖大菠萝辅助器we... 透牌教程!哈糖大菠萝辅助器wepoker到底能不能透视(都是真的有挂);1、首先打开哈糖大菠萝辅助器...
2025新版技巧!wpk模拟器... 2025新版技巧!wpk模拟器是什么天天畅玩德州有挂吗(好像真的有挂);1、首先打开wpk模拟器是什...
新版2025教程!wepoke... 新版2025教程!wepoker有没有透视方法wpk德州辅助(的确是有挂的)1、点击下载安装,wep...
扑克教程!!impoker辅助... 扑克教程!!impoker辅助wepoker私人局作弊开挂方法(其实真的有挂);一、impoker辅...
wpk教程!pokemmo脚本... wpk教程!pokemmo脚本手机版wepoker德州开挂辅助方法(的确是有挂的)1、构建自己的po...
攻略教程!!菠萝辅助器免费版的... 攻略教程!!菠萝辅助器免费版的功能介绍德州大菠萝摆牌攻略(一贯真的有挂)1)菠萝辅助器免费版的功能介...