Ilya And The Tree CodeForces - 842C

（（半個）智商題，主要難度在於實現）

題意：有一棵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;
}