[LOJ 6159] 最长树链

看到要求gcd不为1所以肯定在这条答案链上都是一个质数的倍数，所以就会产生一个很暴力的想法

没错，正解就是这样的暴力

只让走是i(素数)倍数的点，作最长链

最长链可以树形dp或两遍bfs，一遍找端点，一遍过长度即可

复杂度:未证

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

map<int,int> ma;

struct node{

    int u,v,nex;

}x[];

int cnt,n,head[];

void add(int u,int v)

{

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

int v[],sry,have[];

int vis[];

int dis[];

vector<int> ve[];

int vis1[];

int maxn;

int bfs(int u)

{

    queue<int> que;

    int ans=u;

    que.push(u);

    vis[u]=,dis[u]=;

    while(!que.empty())

    {

        int xx=que.front();que.pop();

        for(int i=head[xx];i!=-;i=x[i].nex)

        {

            if(have[x[i].v]==) continue;

            if(vis[x[i].v]) continue;

            vis[x[i].v]=;

            dis[x[i].v]=dis[xx]+;

            if(dis[x[i].v]>dis[ans]) ans=x[i].v;

            que.push(x[i].v);

        }

    }

    while(!que.empty()) que.pop();

    que.push(ans),vis1[ans]=,dis[ans]=;

    while(!que.empty())

    {

        int xx=que.front();que.pop();

        for(int i=head[xx];i!=-;i=x[i].nex)

        {

            if(have[x[i].v]==) continue;

            if(vis1[x[i].v]) continue;

            dis[x[i].v]=dis[xx]+;

            vis1[x[i].v]=;

            if(dis[x[i].v]>dis[ans]) ans=x[i].v;

            que.push(x[i].v);

        }

    }

    return dis[ans];

}

int main()

{

    memset(head,-,sizeof(head));

    n=read();

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

    {

        int u=read(),v=read();

        add(u,v),add(v,u);

    }

    for(int i=;i<=n;i++) v[i]=read();

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

    {

        int x=v[i];

        for(int j=;j<=sqrt(x);j++)

        {

            if(x%j!=) continue;

            if(ma[j]==) ma[j]=++sry;

            ve[ma[j]].push_back(i);

            while(x%j==) x/=j;

        }

        if(x!=)

        {

            if(ma[x]==) ma[x]=++sry;

            ve[ma[x]].push_back(i);

        }

    }

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

    {

        int size=ve[i].size();

        for(int j=;j<size;j++) have[ve[i][j]]=,vis[ve[i][j]]=,vis1[ve[i][j]]=;

        for(int j=;j<size;j++)

        {

            if(vis[ve[i][j]]==) continue;

            maxn=max(maxn,bfs(ve[i][j]));

        }

        for(int j=;j<size;j++) have[ve[i][j]]=,vis[ve[i][j]]=,vis1[ve[i][j]]=;

    }

    cout<<maxn;

}