Ilya And The Tree CodeForces - 842C

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

新老客户大回馈,云服务器低至5折

((半个)智商题,主要难度在于实现)

题意:有一棵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;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:nlog(n)排序

下一篇:hdu 1754 I hate it