学生成绩管理系统网站建设,公司高端网站设计公司,职业技能证书查询入口,南宁seo服务公司题目链接
从大到小枚举gcd的值 d d d#xff0c;以及编号为 d d d的倍数的点#xff0c; [ d , 2 d , 3 d , … ] [d,2d,3d,\dots] [d,2d,3d,…]。 然后对于任何一条边 ( x , y ) (x,y) (x,y)#xff0c;如果 x x x的子树和 y y y的子树里都有编号为 d d d倍数的点#xf…题目链接
从大到小枚举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的倍数的点之后将这些点之间的路径都遍历一遍并合并起来。
#includebits/stdc.h
using namespace std;
const int maxn1e65;
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]);
}
vectorint 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(vfa)continue;dfs(v,u);}
}
int ind[maxn],ans[maxn];
signed main(){int size(25620); //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);cint;while(t--){cinn;for(int i1;in;i)g[i].clear();for(int i1;in;i){cineu[i]ev[i];g[eu[i]].push_back(ev[i]);g[ev[i]].push_back(eu[i]);}dfs(1,0);for(int i1;in;i){if(dep[eu[i]]dep[ev[i]]){ind[eu[i]]i;}else{ind[ev[i]]i;}}for(int i1;in;i)f[i]i;for(int dn/2;d1;d--){int xfind(d);for(int jdd;jn;jd){int yfind(j);while(x!y){if(dep[x]dep[y])swap(x,y);ans[ind[y]]d;f[y]find(par[y]);yfind(par[y]);}}}for(int i1;in;i)printf(%d ,ans[i]);puts();}exit(0);//return 0;
}
每条边只会被合并一次然后枚举倍数的时间开销也是调和级数所以总复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
