http://codeforces.com/contest/842/problem/C 给定一个树，树上每个点有一定价值。 这个点上的魅力值是 从1到这个点的路径 上的所有点价值的gcd。 你有一个操作，可以选择是否要把其中一个点的价值变成0。也就是不影响他的gcd。可以理解为每次求 一个点的魅力值时，都是独立的（也就是你在求一个点的时候，可以把一个点变成0，再求另一个点的魅力值时，可以选择其他点变成0，） 两种写法 一种是用set保留所有状态，（肯定在2e5之内）。 然后输出最大的。。 这个其实挺好的， 还有一种写法就比较的细腻，搜索时同时判断是否要变成0，我感觉这个也挺好。有机会补。 blog.csdn.net/shili_xu/article/details/77714112
#include <bits/stdc++.h> using namespace std; const int maxn=2e5+1000; vector<int>G[maxn]; int a[maxn]; set<int>se[maxn]; int m; int gcd(int m,int n){ if(n==0) return m; else return gcd(n,m%n); } int dfs(int u,int fa,int GCd){ set<int>::iterator i; for(i=se[fa].begin();i!=se[fa].end();i++){ se[u].insert(__gcd(a[u],(*i))); } se[u].insert(GCd); GCd=__gcd(GCd,a[u]); se[u].insert(GCd); for(int i=0;i<G[u].size();i++){ int to=G[u][i]; if(to==fa) continue; dfs(to,u,GCd); } } int main() { int a1,b1; while(~scanf("%d",&m)){ for(int i=1;i<=m;i++){ scanf("%d",&a[i]); } for(int i=1;i<m;i++){ scanf("%d%d",&a1,&b1); G[a1].push_back(b1); G[b1].push_back(a1); } dfs(1,0,0); for(int i=1;i<=m;i++) printf("%d ",*se[i].rbegin()); for(int i=0;i<maxn;i++){ G[i].clear(); se[i].clear(); } } return 0; }