做的时候没看懂题目 看看题解，也挺简单，而且暴力也可以搞过。。。 附个题解：http://blog.csdn.net/xs18952904/article/details/77727920 最近熬夜熬虚了，啥都不想干。
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5+10; vector<int> G[MAXN]; int cnt[MAXN]; int value[MAXN]; int res[MAXN]; int gcd(int a, int b) { if(a == 0 || b == 0) return max(a,b); return __gcd(a,b); } void dfs(int u, int g, int dep, int fa) { int len = G[u].size(); res[u] = g; int num = value[u]; for(int i = 1; i*i <= num; ++i) { if(num%i == 0) { if(i*i == num) { cnt[i]++; if(cnt[i] >= dep) res[u] = max(res[u],i); } else { cnt[i]++; if(cnt[i] >= dep) res[u] = max(res[u],i); cnt[num/i]++; if(cnt[num/i] >= dep) res[u] = max(res[u],num/i); } } } for(int i = 0; i < len; ++i) { if(G[u][i] == fa) continue; dfs(G[u][i],gcd(g,value[u]),dep+1,u); } for(int i = 1; i*i <= num; ++i) { if(num%i == 0) { if(i*i == num) cnt[i]--; else { cnt[i]--; cnt[num/i]--; } } } } int main() { ios::sync_with_stdio(false); int n,a,b; cin >> n; for(int i = 1; i <= n; ++i) cin >> value[i]; for(int i = 1; i < n; ++i) { cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } dfs(1,0,0,-1); for(int i = 1; i <= n; ++i) cout << res[i] << " "; cout << endl; return 0; }