首页 > > 程序设计 > C/C++ >

Ilya And The Tree CodeForces - 842C

2018-06-17 21:58:17来源：未知阅读 ()

（（半个）智商题，主要难度在于实现）

题意：有一棵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用错，打挂

事实上，set还有map的遍历都很容易写错，要小心。

#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;
}