题意
给一棵树求每个点到根的路上允许修改一个为0，gcd的最大值。
题解
g是从根到当前点允许修改的最大gcd，gs为不修改的最大gcd。枚举当前点的因子，更新路径上每个因子出现次数，回溯时减去。并用这个因子更新答案。另外当前点修改为0时，还要用父节点的gs更新答案。复杂度(O(nsqrt n))
代码
代码语言：javascript复制const int N=201000;
int n;
int a[N];
int u,v;
VI e[N];
int g[N],gs[N];
int p[N];
void dfs(int x,int fa,int dep){
for(int i=1;(ll)i*i<=a[x]; i)if(a[x]%i==0){
p[i];if(i*i!=a[x]) p[a[x]/i];
if(p[i]>=dep-1) g[x]=max(g[x],i);
if(p[a[x]/i]>=dep-1) g[x]=max(g[x],a[x]/i);
}
g[x]=max(gs[fa],g[x]);
gs[x]=__gcd(a[x],gs[fa]);
for(auto &v:e[x])if(v!=fa)
dfs(v,x,dep 1);
for(int i=1;(ll)i*i<=a[x]; i)if(a[x]%i==0){
--p[i];if(i*i!=a[x])--p[a[x]/i];
}
}
int main() {
while(~scanf("%d",&n)){
mem(g,0);mem(gs,0);
rep(i,1,n 1)scanf("%d",a i),e[i].clear();
rep(i,0,n-1)scanf("%d%d",&u,&v),e[u].pb(v),e[v].pb(u);
g[0]=gs[0]=a[1];
dfs(1,0,1);
rep(i,1,n 1)printf("%d%c",g[i],i==n?'n':' ');
}
return 0;
}
