从根节点开始维护一个set，表示如果在该路径上将某点置为0后有多少种可能的gcd,然后在用参数传一个从根到上一个点不用0的gcd,实际上，这个set应该不超过2个（不考虑1），每个点的最大可能值就是和set里的做gcd或者考虑把当前点置为0。
#include<bits/stdc++.h> using namespace std; #define MAXN 500005 vector<int> v[MAXN]; int val[MAXN]; int vis[MAXN]; set<int> st[MAXN]; set<int>::iterator it; int gcd(int m,int n) { return n?gcd(n,m%n):m; } template <class T> inline void scan_d(T &ret) { char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9') { ret = ret * 10 + (c - '0'), c = getchar(); } } void dfs(int rt,int fa,int g) //a是用过，b是不用 { //cout<<"rt="<<rt<<" a="<<a<<" b="<<b<<endl; for(it=st[fa].begin();it!=st[fa].end();it++) { int z=gcd(*it,val[rt]); vis[rt]=max(vis[rt],z); if(z!=1) { st[rt].insert(z); } } if(g!=1) { st[rt].insert(g); } vis[rt]=max(vis[rt],g); if(!st[rt].size()) return; for(int i=0;i<v[rt].size();i++) { if(vis[v[rt][i]]) continue; dfs(v[rt][i],rt,gcd(g,val[rt])); } } int main() { memset(vis,0,sizeof(vis)); int n; scan_d(n); for(int i=1;i<=n;i++) { scan_d(val[i]); } int a,b; for(int i=0;i<n-1;i++) { scan_d(a); scan_d(b); v[a].push_back(b); v[b].push_back(a); } st[1].insert(0); // st[1].insert(val[1]); vis[1]=val[1]; for(int i=0;i<v[1].size();i++) { dfs(v[1][i],1,val[1]); } for(int i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",max(1,vis[i])); }