（（半个）智商题，主要难度在于实现）
题意：有一棵n个结点组成的树，其根是编号为1的结点。对于每一个结点，生成从根结点走到这个结点的路径（包括自身），选择路径上的一个点或者不选择任何点，使得其它点的最大公约数最大。每一个结点要分开考虑。
曾经错误做法：
ans[x][0]表示走到x点不选择任何点的最大，ans[x][1]表示走到x点选择1个点的最大。
ans[x][0]=gcd(ans[fa[x]][0],a[x])
ans[x][1]=max(ans[fa[x]][0],gcd(ans[fa[x]][1],a[x]))
错的地方：
如果a>=b,那么gcd(a,c大于等于gcd(b,c)
举例：有一棵树2-3-4，对于4会得出1，正确是2。
错误2：set用错，打挂
#include<cstdio> #include<algorithm> #include<set> using namespace std; struct Edge { int to,next; bool type; }edge[420000]; int n; int first[210000],a[210000],num_edge; bool vis[210000]; int fa[210000]; int ans0[210000]; set<int> ans1[210000];//记录每个结点可能得到的所有gcd值 //set<int>::iterator iter; int gcd(int a,int b) { int t; while(b!=0) { t=a; a=b; b=t%b; } return a; } int dfs(int x) { vis[x]=true; int k=first[x]; ans0[x]=gcd(ans0[fa[x]],a[x]); ans1[x].insert(ans0[fa[x]]); set<int>::iterator iter=ans1[fa[x]].begin(); while(iter!=ans1[fa[x]].end()) { ans1[x].insert(gcd(*iter,a[x])); iter++; } while(k!=0) { if(!vis[edge[k].to]) { fa[edge[k].to]=x; dfs(edge[k].to); } k=edge[k].next; } } int main() { int i,x,y,k; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<n;i++) { scanf("%d%d",&x,&y); edge[++num_edge].to=y; edge[num_edge].next=first[x]; first[x]=num_edge; edge[++num_edge].to=x; edge[num_edge].next=first[y]; first[y]=num_edge; } ans0[1]=a[1]; ans1[1].insert(0); vis[1]=true; k=first[1]; while(k!=0) { fa[edge[k].to]=1; dfs(edge[k].to); k=edge[k].next; } set<int>::reverse_iterator iter; for(i=1;i<=n;i++) { iter=ans1[i].rbegin(); printf("%d ",max(*iter,ans0[i])); } return 0; }
Ilya And The Tree CodeForces - 842C
原文：http://www.cnblogs.com/hehe54321/p/7481954.html