思路与算法

把边权分解为质数幂。对每个质数p，将含p的边按指数从大到小加入空并查集；第一次连通时的指数e就是该质数在最终答案中的指数。把各p^e相乘；原图不连通时输出0。

正确性说明

任一树所有边GCD中p的指数，是树边各指数的最小值；所有树这些GCD的LCM中p的指数则是该最小值的最大可能值。存在所有边均被p^e整除的生成树，当且仅当这些可用边组成的子图连通。按指数降序的首次连通恰给出最大e，各质数的最大值可以来自不同生成树，符合LCM定义。

复杂度

设U=32767、π(U)为质数个数。筛及边分解O(U+M log U)，每个质数初始化并查集至多O(N)，全部整除边条目至多O(M log U)，总可界为O(U+π(U)N+M log U·α(N))，空间O(U+N+M log U)。代码先跳过不足N-1条边的质数，可减少初始化。

易错点

这是所有生成树GCD的LCM，不能求一棵普通MST。不同质数可对应不同树。答案允许到2^64-1，用无符号64位与128位中间乘积。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    struct E {
        int u, v, w;
    };
    vector<E> e(m);
    const int U = 32767;
    vector<int> spf(U + 1), primes;
    for (int i = 2; i <= U; i++) {
        if (!spf[i]) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || i * p > U)
                break;
            spf[i * p] = p;
        }
    }
    vector<vector<int>> bucket(U + 1);
    vector<int> all(n), sz(n, 1);
    iota(all.begin(), all.end(), 0);
    function<int(int)> find = [&](int x) {
        return all[x] == x ? x : all[x] = find(all[x]);
    };
    auto unite = [&](int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return false;
        if (sz[u] < sz[v])
            swap(u, v);
        all[v] = u;
        sz[u] += sz[v];
        return true;
    };
    int count = n;
    for (int i = 0; i < m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        --e[i].u;
        --e[i].v;
        if (unite(e[i].u, e[i].v))
            --count;
        int w = e[i].w;
        while (w > 1) {
            int p = spf[w], power = 1;
            while (w % p == 0) {
                w /= p;
                power *= p;
            }
            bucket[power].push_back(i);
        }
    }
    if (count > 1) {
        cout << 0 << '\n';
        return 0;
    }
    unsigned long long ans = 1;
    for (int p : primes) {
        vector<int> powers;
        int edges = 0;
        for (int power = p; power <= U;) {
            powers.push_back(power);
            edges += bucket[power].size();
            if (power > U / p)
                break;
            power *= p;
        }
        if (edges < n - 1)
            continue;
        iota(all.begin(), all.end(), 0);
        fill(sz.begin(), sz.end(), 1);
        count = n;
        for (auto it = powers.rbegin(); it != powers.rend(); it++) {
            for (int id : bucket[*it])
                if (unite(e[id].u, e[id].v))
                    --count;
            if (count == 1) {
                __uint128_t product = (__uint128_t)ans * (*it);
                assert(product <= numeric_limits<unsigned long long>::max());
                ans = product;
                break;
            }
        }
    }
    cout << ans << '\n';
}