题目描述

给你个节点的一棵树，还有每个点的点权值，现在要你选出一条最长的边，保证这条边中全部的点之后的值不等于，也就是存在一个公共的因子全部点都有。

Solution

思路参考喵渺淼妙的死忠粉大佬这是原题解传送门
观察到这个问题，那么我们第一步想想能不能去枚举，根据唯一分解定理，每一个数都可以拆成一堆质因数幂积的形式。那么现在再看给我们的这棵树，如果把他分解质因数之后，那么可以和它构成一条链的节点一定也存在这些质因数中的一个。那么我们就可以使用一个表，保存全部节点的质因子，我们接下来就可以去枚举这些因子了。那么再枚举这些因子的条件后就变成了求最大的连接的链是多长了，对每个有孩子的子树记录下子树最长的单链，找到最长的两个链连接就行。这个走个即可，关键性的时间复杂度还是前面那个分解全部的数的因子条件，可以看到最极端的情况，个数全部都是大素数里面有个素数，并且都是最接近的那个素数，那么还是会死）大概。那就要加上一个特判大素数的地方，(模板)米勒罗宾素数测试官方题解没加探测函数，然后用我自己的板子发现本来不的加了反而飞了。。就参考了一下YangYL°大佬的板子，把他套在分解质因子前面，好在不炸。

1/14 数据更新了，好像蜜汁卡死了。。等我再看看什么地方死了，待更新。只有87分。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 32000 + 7; // sqrt(1e9)
const int M = 1e5 + 7;

vector<int>    prime;
int cnt, n, m;
bool vis[M];

void getprime() { // 欧拉筛法求素数表O(n)
    memset(vis, true, sizeof(vis));
    cnt = 0;
    for (int i = 2; i < N; ++i) {
        if (vis[i]) prime.push_back(i), ++cnt;
        for (int j = 0; j < cnt; ++j) {
            if (i * prime[j] >= N) break;
            vis[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
        }
    }
}

/*米勒罗宾素数测试*/
ll A[11] = { 0,2,3,5,7,11,13,17,19,23,61 };
int Miller_Rabin(int 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 = qpow(A[j], p, x);
        for (int i = 1; i <= s; i++) {
            long long K = (B * B) % x;
            if (K == 1ll && B != 1ll && B != x - 1) return 0;//如果二次探测发现这个不是质数
            B = K;
        }
        if (B != 1ll) return 0;
    }
    return 1;//探测正常结束
}

int head[M], tot = 0;//前向星变量
struct Node {
    //int u; //起点
    //int w; //权值
    int v, next;
} edge[M << 1];

void add(int u, int v) {
    tot++;
    //edge[tot].u = u;
    edge[tot].v = v;
    //edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot;
}
unordered_map<int, vector<int>> has;
int w[M], ans = 1;

int dfs(int u, int num) {
    if (w[u] % num != 0)    return 0;
    vis[u] = 1;
    int res = 1;
    int max1 = -1, max2 = -1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (!vis[v]) {
            int tmp = dfs(v, num);
            res = max(res, 1 + tmp);
            if (tmp >= max1)    max2 = max1, max1 = tmp;
            else if (tmp >= max2)    max2 = tmp;
        }
    }
    if (max1 != -1 and max2 != -1)    ans = max(ans, max1 + max2 + 1);
    else if (max1 != -1)    ans = max(ans, max1);
    return res;
}

void solve() {
    getprime();
    n = read();
    rep(i, 1, n - 1) {
        int u = read(), v = read();
        add(u, v); add(v, u);
    }
    for (int i = 1; i <= n; ++i) {
        w[i] = read();
        int tmp = w[i];
        if (Miller_Rabin(tmp)) {
            prime.push_back(tmp), has[tmp].push_back(i), ++cnt; // 大素数
            continue;
        }
        for (int j = 0; j < cnt; ++j) {
            if (tmp == 1)    break;
            if (tmp % prime[j] == 0) {
                has[prime[j]].push_back(i);
                while (tmp % prime[j] == 0)    tmp /= prime[j];
            }
        }
        if (tmp != 1)    prime.push_back(tmp), has[tmp].push_back(i), ++cnt;
    }
    for (auto& it : prime) {
        ms(vis, 0);
        for (auto& pos : has[it])
            if (!vis[pos])    dfs(pos, it);
    }
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}