因为我太菜了，于是乎就找了份代码，理解了一下思路（把坑填完才能好好复习zz

思路：

  • 1.先用筛求质数表,表长大约是sqrt(1e9)
  • 2.建树
  • 3.对权值进行质因数分解，并把对应的权值下标与素数对应起来存下来
  • 4.然后树形dp求符合条件的最长链

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=31624;
struct node{
    int v,nex;
}t[N<<1];
int val[N][10],tot[N];
int zhi[M],e,dp[N][10];
int las[N],len;bool f[M];
inline void add(int u,int v){
    t[++len]=(node){v,las[u]},las[u]=len;
}
inline void sai(int maxe){
    for(int i=2;i<=maxe;++i){
        if(!f[i])zhi[++e]=i;
        for(int j=1;j<=e;++j){
            if(i*zhi[j]>maxe)break;
            f[i*zhi[j]]=1;
            if(i%zhi[j]==0)break;
        }
    }
}
int ans=1;
inline void dfs(int x,int fa){
    for(int i=1;i<=tot[x];++i){
        dp[x][i]=1;
    }
    for(int i=las[x];i;i=t[i].nex){
        int v=t[i].v;
        if(v!=fa){
            dfs(v,x);
            for(int j=1;j<=tot[x];++j){
                for(int k=1;k<=tot[v];++k){
                    if(val[x][j]==val[v][k]){
                        ans=max(ans,dp[x][j]+dp[v][k]);
                        dp[x][j]=max(dp[x][j],dp[v][k]+1);
                    }
                }
            }
        }
    }
}
int main(){
    sai(M-1);
    //每个点最多由9个不同质数
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i){
        int x;
        scanf("%d",&x);
        for(int j=1;j<=e;++j){
            if(x<zhi[j])break;
            if(x%zhi[j]==0){
                val[i][++tot[i]]=zhi[j];
                while(x%zhi[j]==0)x/=zhi[j];
            }
        }
        if(x>1){
            val[i][++tot[i]]=x;
        }
    }
    dfs(1,1);
    printf("%d",ans);
    return 0;
}