C题解:有一棵树,一开始每个点有一个初始值,每一个点的新数为它到树顶的路径中的所有数,去掉一个数后的最大公因数中的最大值
程序员文章站
2022-07-07 22:33:56
题意
有一棵树,一开始每个点有一个初始值,每一个点的新数为它到树顶的路径中的所有数,去掉一个数后的最大公因数中的最大值.
做法
因为要去掉一个数,所以一个个枚...
题意
有一棵树,一开始每个点有一个初始值,每一个点的新数为它到树顶的路径中的所有数,去掉一个数后的最大公因数中的最大值.
做法
因为要去掉一个数,所以一个个枚举显然不显示,因而可以在dfs时记录一下此时的点到根的数的因数个数,也就是每扫到一个点都将其分解质因数(记得回溯),若新增的因数的个数达到其深度-1,则这个数可用,在分解的同时找到最大的.
但还要考虑不是新增的因数,即去掉的数是这个点的数,那么此时的答案为其父节点到根 的所有数中的最大公约数,比较两个数取最大值即可.
代码
#include<iostream> #include<cstdio> #include<cstring> #define N 200100 using namespace std; int n,m,dn[N],bb,first[N],g[N],deep[N],cnt[N],ans[N]; struct Bn { int to,next; }bn[N*2]; inline void add(int u,int v) { bb++; bn[bb].to=v; bn[bb].next=first[u]; first[u]=bb; } inline int fj(int u,int v) { int i,res=1; cnt[u]++; if(cnt[u]>=v) res=u; for(i=2;i*i<=u;i++) { if(u%i==0) { cnt[i]++; if(cnt[i]>=v) res=max(res,i); if(i*i!=u) { cnt[u/i]++; if(cnt[u/i]>=v) res=max(res,u/i); } } } return res; } inline void ffj(int u) { int i; cnt[u]--; for(i=2;i*i<=u;i++) { if(u%i==0) { cnt[i]--; if(i*i!=u) { cnt[u/i]--; } } } } inline int gcd(int u,int v) { if(u<v) swap(u,v); for(;u!=v&&u&&v;swap(u,v)) { u%=v; } return max(u,v); } void dfs(int now,int last) { int p,q; for(p=first[now];p!=-1;p=bn[p].next) { if(bn[p].to==last) continue; deep[bn[p].to]=deep[now]+1; g[bn[p].to]=gcd(dn[bn[p].to],g[now]); ans[bn[p].to]=fj(dn[bn[p].to],deep[now]); ans[bn[p].to]=max(ans[bn[p].to],g[now]); dfs(bn[p].to,now); ffj(dn[bn[p].to]); } } int main() { memset(first,-1,sizeof(first)); register int i,j,p,q; cin>>n; for(i=1;i<=n;i++) { scanf("%d",&dn[i]); } for(i=1;i<n;i++) { scanf("%d%d",&p,&q); add(p,q); add(q,p); } deep[1]=1; g[1]=ans[1]=dn[1]; fj(dn[1],1); dfs(1,-1); for(i=1;i<=n;i++) { printf("%d ",ans[i]); } }