欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C题解:有一棵树,一开始每个点有一个初始值,每一个点的新数为它到树顶的路径中的所有数,去掉一个数后的最大公因数中的最大值

程序员文章站 2022-07-07 22:33:56
题意 有一棵树,一开始每个点有一个初始值,每一个点的新数为它到树顶的路径中的所有数,去掉一个数后的最大公因数中的最大值. 做法 因为要去掉一个数,所以一个个枚...

题意

有一棵树,一开始每个点有一个初始值,每一个点的新数为它到树顶的路径中的所有数,去掉一个数后的最大公因数中的最大值.

做法

因为要去掉一个数,所以一个个枚举显然不显示,因而可以在dfs时记录一下此时的点到根的数的因数个数,也就是每扫到一个点都将其分解质因数(记得回溯),若新增的因数的个数达到其深度-1,则这个数可用,在分解的同时找到最大的.

但还要考虑不是新增的因数,即去掉的数是这个点的数,那么此时的答案为其父节点到根 的所有数中的最大公约数,比较两个数取最大值即可.

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200100
using namespace std;

int n,m,dn[N],bb,first[N],g[N],deep[N],cnt[N],ans[N];
struct Bn
{
    int to,next;
}bn[N*2];

inline void add(int u,int v)
{
    bb++;
    bn[bb].to=v;
    bn[bb].next=first[u];
    first[u]=bb;
}

inline int fj(int u,int v)
{
    int i,res=1;
    cnt[u]++;
    if(cnt[u]>=v) res=u;
    for(i=2;i*i<=u;i++)
    {
        if(u%i==0)
        {
            cnt[i]++;
            if(cnt[i]>=v) res=max(res,i);
            if(i*i!=u)
            {
                cnt[u/i]++;
                if(cnt[u/i]>=v) res=max(res,u/i);
            }
        }
    }
    return res;
}

inline void ffj(int u)
{
    int i;
    cnt[u]--;
    for(i=2;i*i<=u;i++)
    {
        if(u%i==0)
        {
            cnt[i]--;
            if(i*i!=u)
            {
                cnt[u/i]--;
            }
        }
    }
}

inline int gcd(int u,int v)
{
    if(u<v) swap(u,v);
    for(;u!=v&&u&&v;swap(u,v))
    {
        u%=v;
    }
    return max(u,v);
}

void dfs(int now,int last)
{
    int p,q;
    for(p=first[now];p!=-1;p=bn[p].next)
    {
        if(bn[p].to==last) continue;
        deep[bn[p].to]=deep[now]+1;
        g[bn[p].to]=gcd(dn[bn[p].to],g[now]);

        ans[bn[p].to]=fj(dn[bn[p].to],deep[now]);
        ans[bn[p].to]=max(ans[bn[p].to],g[now]);
        dfs(bn[p].to,now);
        ffj(dn[bn[p].to]);
    }
}

int main()
{
    memset(first,-1,sizeof(first));
    register int i,j,p,q;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&dn[i]);
    }
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&p,&q);
        add(p,q);
        add(q,p);
    }
    deep[1]=1;
    g[1]=ans[1]=dn[1];
    fj(dn[1],1);
    dfs(1,-1);
    for(i=1;i<=n;i++)
    {
        printf("%d ",ans[i]);
    }
}