前言:

之前那个博客有大问题...确实是数据太水了.

思路:

首先我们处理出4e4以内的质数,然后因为任何合数都可以写成的形式,显然大于4e4的数,假如经过这么一次筛选,一定是不会出现超过4e4的合数.对于每个数,我们处理出来它们的质因子,这里呢,用的是最原始的判断方法,假如有n个数是大质数,那么就高达了.所以假如这样的话,最好还得套个米可罗宾先判断它是不是大质数.后面对于每个质因子搜其点,找到两条最长链即可了(随便树形dp一下).因为一个数的质因子个数最多不超过30个(1e9以内.)所以你的搜索上线也就.然后就得以解决此问题.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,MM=1e5;
int w[N];
vector<int>g[N];
//map<int,vector<int> >s;
unordered_map<int,vector<int> >s;
int Ans = 1,Mod,A[11] = {0,2,3,5,7,11,13,17,19,23,61}; // A就是Miller Rabin 探测的底数
bool vis[N];
int Prime[N],tot = 0 ,cnt = 0,book[N];
int prime[N*10];
unordered_map<int,bool> M;//记录哪一些质因子出现过
void GetPrime() {
    for(int i = 2 ; i <=4e4 ; i ++) {
        if(!book[i]) Prime[++cnt] = i;
        for(int j = 1 ; j <= cnt ; j ++) {
            if(Prime[j] * i > 4e4) break;
            book[Prime[j] * i] = 1;
            if(i % Prime[j] == 0) break;
        }
    }
    return ;
}

long long quickpower(long long x,long long y) {
    long long ans = 1 , op = x;
    while(y) {
        if(y & 1ll) ans *= op , ans %= Mod;
        op *= op , op %= Mod;
        y >>= 1ll;
    }
    return ans;
}

int Miller_Rabin(int x) {//素数探测算法
    Mod = x;
    int s = 0;
    if(x == 2) return 1;
    if(x % 2 == 0 || x == 1) return 0;
    int p = x - 1 ;
    while(p % 2 == 0) p/= 2 , s ++;
    for(int j = 1 ; j <= 5 ; j ++) {
        long long B = quickpower(A[j] , p);
        for(int i = 1 ; i <= s ; i ++) {
            long long K = (B * B) % Mod;
            if(K == 1ll && B != 1ll && B != Mod - 1) return 0;//如果二次探测发现这个不是质数
            B = K;
        }
        if(B != 1ll) return 0;//利用费马小定理判断
    }
    return 1;//探测正常结束
}
int ans=-1;
int dfs(int u,int num)
{
    vector<int>a;
    if(w[u]%num!=0)    return 0;
    vis[u]=true;int res=1;
    for(int x:g[u])
    {
        if(!vis[x])
        {
            int Cnt=dfs(x,num);
            res=max(res,1+Cnt);
            ans=max(ans,res);
            a.push_back(Cnt);
        }
    }sort(a.begin(),a.end());
    int x=a.size();
    if(x>1)   ans=max(ans,a[x-1]+a[x-2]+1);
    return res;
}

int main()
{
    int m=4e4,id=0;GetPrime();
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);int x=w[i];
        if(Miller_Rabin(x))
        {
            s[x].push_back(i);
            if(M[x] != 1) M[x] = 1,prime[++id]=x;
            continue;
        }
        for(int j=1; Prime[j] * Prime[j] <= x;j++)
        {
            if(x%Prime[j]==0)
            {
                s[Prime[j]].push_back(i);
                while(x%Prime[j]==0)    x/=Prime[j];
                if(M[Prime[j]] == 0) M[Prime[j]] = 1 , prime[++id] = Prime[j];
            }
        }if(x != 1) {
            s[x].push_back(i);
            if(M[x] != 1) M[x] = 1 , prime[++id] = x;
        }
    }
    for(int i=1;i<=id;i++)
    {
        for(int j:s[prime[i]])
            if(!vis[j])    dfs(j,prime[i]);
        for(int j:s[prime[i]])    vis[j]=false;
    }printf("%d\n",ans);
    return 0;
}
/*
4
1 2
1 3
1 4
2 2 2 2 
*/