前置知识：

素数判断（ 素数探测可用可不用吧） + + 分组思维

具体做法

观察题目，发现题目要求我们求 不等于 的一条最长链。

那么如果这条链上所有的节点的 都不为 ，那么它们肯定有着至少一个相同的质因子。

所以我们考虑将拥有相同质因子的节点放在一起处理，然后对于具有相同质因子的节点中求一条最长链就行了。

求最长链的过程用 DFS 实现即可。

于是这个题目的解决流程是这样子的：

对于所有的给出的节点的权值进行质因数分解。
有着相同质因子的数我们就放入 map 中，定义一个 <int,vector<int> > 类型的 map 即可。

然后遍历所有出现过的质因子（可以用另外一个数组记录，并且用 map 来防止重复入队）

对于有着相同质因子的所有节点各求最长链。

求出最大值即可。

这个题目的复杂度看似无法保证。但是我们可以分析一下这道题目的最坏情况下的复杂度。（用出数据的人的思维）

我们的主要目标就是要使得 中记录的节点最多。（因为对于 中的节点我们每一个都会访问一次）

那么也就是说，对于同一个数，我们总是希望它被分在不同的组里面，这样子就能使得这个程序被卡(bushi。

但是对于一个 以内的数，它最多有 个不同的质因子，所以整个 中的节点最多是 个，并且我们可以得出使得这个程序跑满的那一个权值：

于是这个题目的最坏复杂度大概就是 ，非极限情况复杂度大概是 ( 是来自 的)。

另外要提一嘴的就是，因为质因数分解的复杂度是 的，假若给定的权值全是很大的质数的话，那么这个程序就会被卡死，所以我的题解里面写了 素数探测算法，官方题解提供者：“代码长了不好看”(结果就被我 了。

Code

// Problem: 最长树链
// Memory Limit: 65536 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 50;
#define int long long 
int n,start[MAXN], data[MAXN];
int Prime[MAXN],tot = 0 ,cnt = 0, book[MAXN];
int vis[MAXN],D[MAXN * 11],dis[MAXN] , tail = 0 , q[MAXN];
int Ans = 1,Mod,A[11] = {0,2,3,5,7,11,13,17,19,23,61}; // A就是Miller Rabin 探测的底数
map <int,vector<int> > mp;
map <int,int > M;//记录哪一些质因子出现过

struct Edge {
    int next,to;
    void add(int from,int To) {to = To , next = start[from], start[from] = tot;}
} edge[MAXN * 2];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

void GetPrime() {
    for(int i = 2 ; i <= 5e4 ; i ++) {
        if(!book[i]) Prime[++cnt] = i;
        for(int j = 1 ; j <= cnt ; j ++) {
            if(Prime[j] * i > 5e4) 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;//探测正常结束
}

void DFS(int x,int P,int from) {
    vis[x] = 1;//处理与 x 点在同一个连通块的情况。
    q[++tail] = x;
    dis[x] = dis[from] + 1;
    for(int i = start[x] ; i ; i = edge[i].next) {
        int to = edge[i].to;
        if(to == from) continue;
        if(data[to] % P == 0)
        DFS(to,P,x);
    }
    return ;
}

int solve(int x,int P) {//笔者采用两次DFS求直径的方法来求出最长链
    tail = 0;
    int ans = 1;
    vis[x] = 1;
    DFS(x,P,0);//进行一次DFS求出离当前点最远的点P
    int f = 0;
    for(int i = 1 ; i <= tail ; i ++)
        if(dis[q[i]] > dis[f]) f = q[i];//找出离自己最远的
        for(int i = 1 ; i <= tail ; i ++) dis[q[i]] = 0;
    tail = 0;
    DFS(f,P,0);//第二次DFS
    f = 0;
    for(int i = 1 ; i <= tail ; i ++) 
        if(dis[q[i]] > dis[f]) f = q[i];//找出离P最远的点Q
    return dis[f];//这个连通块的最长链
}

signed main() {
    n = read();
    GetPrime();
    memset(data,0,sizeof(data));
    for(int i = 1 ; i <= n - 1; i ++) {
        int u = read() , v = read();
        edge[++tot].add(u,v);
        edge[++tot].add(v,u);
    }
    for(int i = 1 ; i <= n ; i ++) data[i] = read();
    cnt = 0;
    for(int i = 1 ; i <= n ; i ++) {
        int x = data[i];
        int p = Miller_Rabin(x);
        if(p == 1) {//如果是质数就直接入列
            mp[x].push_back(i);
            if(M[x] != 1) M[x] = 1 , D[++cnt] = x;
            continue;
        }
        for(int j = 1 ; Prime[j] * Prime[j] <= x ; j ++)
            while(x % Prime[j] == 0) {
                x /= Prime[j] , mp[Prime[j]].push_back(i);
                if(M[Prime[j]] == 0) M[Prime[j]] = 1 , D[++cnt] = Prime[j];
            }
        if(x != 1) {
            mp[x].push_back(i);
            if(M[x] != 1) M[x] = 1 , D[++cnt] = x;
        }
    }
    for(int i = 1 ; i <= cnt ; i ++) {
        int len = mp[D[i]].size();
        for(int j = 0 ; j < len ; j ++)
        if(!vis[mp[D[i]][j]]) Ans = max (Ans , solve(mp[D[i]][j],D[i])) ;
        for(int j = 0 ; j < len ; j ++) vis[mp[D[i]][j]] = 0 , dis[mp[D[i]][j]] = 0;
    }
    cout << Ans;
    return 0;
}
/*
4
1 2
1 3
1 4
2 2 2 2//这是一组 Hack 数据
*/