「美团 CodeM 初赛 Round A」最长树链

题目描述

Mr. Walker 最近在研究树，尤其是最长树链问题。现在树中的每个点都有一个值，他想在树中找出最长的链，使得这条链上对应点的值的最大公约数不等于1。请求出这条最长的树链的长度。

输入格式

第一行一个整数 n，表示点的个数。

接下来 n−1 行，每行两个整数 x,y 表示 x,y 之间有边。

数据保证给出的是一棵树。

接下来一行 n 个整数表示每个点对应的权值 ai。

输出格式

输出一个整数，表示这条树链的长度。

样例

样例输入

1 2

1 3

2 4

6 4 5 2

样例输出

数据范围与提示

n<=10^5,1<= ai<=10^9。

【题解】

做这类题一定要记住这句话：

没有暴力解决不了的题，只有不敢写暴力的人！

咳咳，所以说，这题的正解正是暴力。

读完题后，我们不难想到这样一个暴力：枚举每一个质数，权值是这个质数的倍数的节点设为1，最长链的长度就是点权为1的点构成的最长的链。

如果枚举所有质数，这题就会变成n*n，一定是A不了的，那怎么办呢？方法是这样的。

每个数最多只有log个不同的质因数，所以只要把所有点权质因数分解，枚举出现的质数就可以了。

我们枚举完质因数后dfs，因为每个点最多有log个不同的质因数，所以复杂度大概是O（能过）O（nlogn）。

【题外话】

这么写有一些小问题，如果质数极大就会T，Loj是能A的（数据真垃圾），但吕神的数据比较优秀，把我卡成了75.

这题告诉我：永远不要被数据吓到，也永远不要放弃一题，万一打个暴力能A呢？

下贴本蒟蒻丑陋的代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

const int N=;

int n,con,ans=,h[N],cnt,a[N],p[N],dis[N];

bool v[N];

struct

{

    int nex,to;

}e[N<<];

void dfs(int u,int b,int c)

{

    dis[u]=;

    for(int i=h[u];i;i=e[i].nex)

        if(e[i].to!=b && a[e[i].to]%c==)

        {

            while(a[e[i].to]%c==)

              a[e[i].to]/=c;

            dfs(e[i].to,u,c);

            ans=max(ans,dis[u]+dis[e[i].to]+);

            dis[u]=max(dis[u],dis[e[i].to]);

        }

    dis[u]++;

}

void add(int u,int v)

{

    cnt++;

    e[cnt].nex=h[u];

    e[cnt].to=v;

    h[u]=cnt;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i*i<=;i++)

      if(v[i]==)

      {

          for(int j=i*i;j<;j+=i) v[j]=;

      }

    for(int i=;i<=;i++)

      if(v[i]==)

        p[++con]=i;

    for(int i=;i<n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    for(int i=;i<=n;i++)

      scanf("%d",&a[i]);

    for(int i=;i<=n;i++)

    {

        int s=a[i];

        for(int j=;j<=con && p[j]*p[j]<=a[i];j++)

        {

            if(s%p[j]==)

            {

                while(s%p[j]==)

                  s/=p[j];

                dfs(i,,p[j]);

            }

        }

        if(s>)

          dfs(i,,s);

        a[i]=;

    }

    printf("%d",ans);

    return ;

}

oi路漫漫，愿此题解能助你一臂之力......

巴特西

「美团 CodeM 初赛 Round A」最长树链

最新文章

热门文章