最长树链【米勒罗宾+树的直径的简单树形DP】

很容易想到正确的解法，首先，我们可以知道（2 * 3 * 5 * 7 * 11 * 13 * ……）最多19个质数相乘就会达到1e9级别的。于是，我们可以考虑质数，我们可以知道一个数最多就是分成20个质数，所以我们直接进行对质数的检验会好一些。但是有些大质数应该怎么办呢？于是就有了米勒罗宾检验素数。此处套个板子……
然后，我们对于每一个质数，我们去求一个每一个相连子树的最长的树的直径即可，此处可用树形DP，或者跑两次dfs任意，都是O(N)。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define pii pair<int, int>
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
namespace Mile
{
    const int count = 5;
    ll modular_exp(int a, int m, int n)
    {
        if(m == 0) return 1;
        if(m == 1) return (a % n);
        long long w = modular_exp(a, m/2, n);
        w = w * w % n;
        if(m & 1) w = w * a % n;
        return w;
    }
    bool Miller_Rabin(int n)
    {
        if(n == 2) return true;
        for(int i = 0; i < count; i ++)
        {
            int a = rand() % (n - 2) + 2;
            if(modular_exp(a, n, n) != a) return false;
        }
        return true;
    }
}
using namespace Mile;
const int maxN = 1e5 + 7, maxM = 1e4 + 7;
int N, head[maxN], cnt;
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
} edge[maxN << 1];
inline void addEddge(int u, int v)
{
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt ++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
bool vis[32000] = {false};
int Prime[maxM], tot = 0;
inline void init()
{
    cnt = 0;
    for(int i = 1; i <= N; i ++) head[i] = -1;
    for(int i = 2; i <= 31623; i ++)
    {
        if(!vis[i])
        {
            Prime[++ tot] = i;
            for(int j = i * 2; j <= 31623; j += i) vis[j] = true;
        }
    }
}
int a[maxN];
map<int, vector<int>> son;
void Solve(int id)
{
    int x = a[id];
    for(int i = 1; i <= tot && Prime[i] * Prime[i] <= x; i ++)
    {
        if(x == 1) return;
        if(x % Prime[i] == 0)
        {
            son[Prime[i]].push_back(id);
            while(x % Prime[i] == 0) x /= Prime[i];
        }
    }
    if(x > 1) son[x].push_back(id);
}
int ans;
vector<int> used;
bool read[maxN] = {false};
int gcd(int a, int b) { return b ? a : gcd(b, a % b); }
int dfs(int u, int fa, int x)
{
    if(a[u] % x) return 0;
    read[u] = true;
    int maxx = 1;
    for(int i = head[u], v, tmp; ~i; i = edge[i].nex)
    {
        v = edge[i].to;
        if(v == fa) continue;
        tmp = dfs(v, u, x);
        ans = max(ans, tmp + maxx);
        maxx = max(maxx, tmp + 1);
    }
    return maxx;
}
int main()
{
    scanf("%d", &N);
    init();
    for(int i = 1, u , v; i < N; i ++)
    {
        scanf("%d%d", &u, &v);
        _add(u, v);
    }
    for(int i = 1; i <= N; i ++)
    {
        scanf("%d", &a[i]);
        if(Miller_Rabin(a[i]))
        {
            son[a[i]].push_back(i);
        }
        else
        {
            Solve(i);
        }
    }
    ans = 1;
    for(map<int, vector<int>>::iterator it = son.begin(); it != son.end(); it ++)
    {
        for(int u : it->second)
        {
            if(read[u]) continue;
            dfs(u, 0, it->first);
        }
        for(int u : it->second)
        {
            read[u] = false;
        }
    }
    printf("%d\n", ans);
    return 0;
}