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)$。