生成树

GitHub跳转原题关系图返回列表

答案等于所有使「只留权值能被 d 整除的边后图连通」的 d 的最小公倍数,枚举 d 用并查集判连通即可。

OJ: roj

题目 ID: 1713

难度:提高+/省选-

标签:图论并查集数论生成树python

创建: 2026-10-07 17:50

更新: 2026-10-07 17:50

形式化题目

给定一张 NN 个点、MM 条边的无向图(无重边无自环不保证,si≠tis_i \neq t_i), 第 ii 条边有权值 di⩾1d_i \geqslant 1。设图的全部生成树构成集合 T\mathcal{T}, 对每棵生成树 TT 定义

g(T)=gcd⁡{ de:e∈T },g(T) = \gcd\{\, d_e : e \in T \,\},

要求输出

ans=lcm⁡T∈Tg(T).\mathrm{ans} = \operatorname*{lcm}_{T \in \mathcal{T}} g(T).

数据范围:N⩽1000N \leqslant 1000,M⩽100000M \leqslant 100000,1⩽di⩽215−1=327671 \leqslant d_i \leqslant 2^{15} - 1 = 32767, 保证 ans⩽264−1\mathrm{ans} \leqslant 2^{64} - 1。

以样例为例,N=3N = 3 的三条边权为 2,3,62, 3, 6,三棵生成树分别去掉一条边:

生成树 边权集合 g(T)g(T)
去掉 22 {3,6}\{3, 6\} 33
去掉 33 {2,6}\{2, 6\} 22
去掉 66 {2,3}\{2, 3\} 11

lcm⁡(1,2,3)=6\operatorname{lcm}(1, 2, 3) = 6,与输出一致。这里已经能看出难点: T\mathcal{T} 的规模是指数级的(MM 条边取 N−1N-1 条),不可能真的枚举生成树。

正解

思路

从"枚举生成树"改成"枚举因子"。 生成树数量是指数级的,但 g(T)g(T) 的取值只有 1∼327671 \sim 32767 这 3276732767 种可能,而且它只由 TT 的边权集合决定。于是把视角从 “树"换到"数 dd"上:对每个 dd,问"存不存在一棵生成树,它的边权全都被 dd 整除”。

定义 GdG_d 为只保留权值能被 dd 整除的边(即 d∣ded \mid d_e)后得到的子图, 记

D={ d⩾1:Gd 连通 }.D = \{\, d \geqslant 1 : G_d \text{ 连通} \,\}.

则 d∈Dd \in D 与"存在生成树 TT 使 d∣g(T)d \mid g(T)"是同一件事:前者取 GdG_d 的一棵生成树 就得到后者;后者中的 TT 整棵落在 GdG_d 里,故 GdG_d 连通。注意 dd 只需枚举到 wmax⁡=max⁡edew_{\max} = \max_e d_e,因为 d>wmax⁡d > w_{\max} 时 GdG_d 一条边都没有(N⩾2N \geqslant 2 时不连通)。

核心结论。

 ans=lcm⁡d∈Dd \boxed{\ \mathrm{ans} = \operatorname*{lcm}_{d \in D} d\ }

证明。 记 L=lcm⁡d∈DdL = \operatorname*{lcm}_{d \in D} d。

  1. 任取生成树 TT,令 g=g(T)g = g(T)。由 gcd⁡\gcd 的定义 g∣deg \mid d_e 对 TT 的每条边成立, 所以 TT 的每条边都留在 GgG_g 里,TT 是 GgG_g 的生成树,GgG_g 连通,即 g∈Dg \in D。 于是 g∣Lg \mid L。这对每棵 TT 都成立,故 lcm⁡Tg(T)∣L\operatorname*{lcm}_T g(T) \mid L。
  2. 任取 d∈Dd \in D。GdG_d 连通,取它的一棵生成树 TdT_d,则 d∣ded \mid d_e 对 TdT_d 的每条边 成立,故 d∣g(Td)∣lcm⁡Tg(T)d \mid g(T_d) \mid \operatorname*{lcm}_T g(T)。对所有 d∈Dd \in D 取 lcm\mathrm{lcm} 得 L∣lcm⁡Tg(T)L \mid \operatorname*{lcm}_T g(T)。

两向合并即 ans=L\mathrm{ans} = L。■\blacksquare

这个结论的直觉是:gcd⁡\gcd 是"对边权集合取下确界"、lcm\mathrm{lcm} 是"取上确界", 而"整除"这个偏序恰好被"边集包含"→\to"连通性"单调地反映出来——dd 越小边越多、 GdG_d 越容易连通,DD 于是是一个下封闭的集合(d∈Dd \in D、d′∣d⇒d′∈Dd' \mid d \Rightarrow d' \in D), 答案正是它的最小公倍数。也正因为下封闭,DD 由它的极大元决定,但枚举全部 dd 更省事。

怎么判定 d∈Dd \in D? 就是一次连通性检查:把权值为 dd 的倍数的边全部并起来, 看最后连通块个数是否为 11。用并查集维护连通块个数 comp(初值 NN,每次成功合并减一), 最后判 comp == 1。

复杂度怎么压。 朴素地对每个 dd 扫一遍全部 MM 条边是 O(M⋅wmax⁡)=3×109O(M \cdot w_{\max}) = 3 \times 10^9, 太慢。改成按权值分桶:把边按权值排序,再用 cnt[w] / st[w] 记录"权值 ww 的边 在数组中的一段",判定 dd 时直接遍历 k=d,2d,3d,…k = d, 2d, 3d, \dots 这些桶即可。这样每条边 ee 只在 d∣ded \mid d_e 时被访问,总合并次数为

∑eτ(de)≈M⋅τ‾≈105×10,\sum_{e} \tau(d_e) \approx M \cdot \overline{\tau} \approx 10^5 \times 10,

其中 τ\tau 是约数个数。加上每个 dd 一次 O(N)O(N) 的并查集重置,共 O(N⋅wmax⁡)≈3.3×107O(N \cdot w_{\max}) \approx 3.3 \times 10^7。 还有个免费剪枝:若 dd 的所有倍数权值上都没有边,直接跳过、连并查集都不用重置。

答案用无符号 64 位。 题面保证 ans⩽264−1\mathrm{ans} \leqslant 2^{64} - 1,而样例 9 的答案是 18446636557034669317>263−118446636557034669317 > 2^{63} - 1,所以 C++ 里必须用 unsigned long long, 输出格式串是 %llu。另一个细节:按 dd 递增累乘 lcm\mathrm{lcm} 时,每个中间结果都整除 最终答案,所以 ans / gcd(ans, d) * d 不会中途溢出。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 17:50
# update_at: 2026-10-07 17:50

import sys
from math import lcm

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Buckets = dict[int, list[tuple[int, int]]]  # 边权 -> 该权值的边表 [(u, v)]


def find(parent: list[int], x: int) -> int:
    """并查集找根:路径减半,顺路把 x 直挂祖父。"""
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x


def spans(n: int, buckets: Buckets, d: int, maxw: int) -> bool:
    """只保留边权为 d 的倍数的边(记作 G_d)后,整张图是否连通。"""
    parent = list(range(n + 1))
    comp = n  # 当前连通块个数
    for k in range(d, maxw + 1, d):
        edges = buckets.get(k)
        if edges is None:
            continue
        for u, v in edges:
            ru, rv = find(parent, u), find(parent, v)
            if ru != rv:
                parent[rv] = ru
                comp -= 1
        if comp == 1:  # 已经连通,后面那些桶不必再看
            return True
    return comp == 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    buckets: Buckets = {}
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        buckets.setdefault(w, []).append((u, v))

    # n = 1(必然 m = 0)只有唯一的空生成树,约定答案为 1
    if n <= 1 or not buckets:
        print(1)
        return

    maxw = max(buckets)  # d 只需枚举到最大边权,更大的 d 一条可用边都没有
    weight_count = {w: len(edges) for w, edges in buckets.items()}  # 每个权值有几条边
    # avail[d] = 边权能被 d 整除的边数(下标 0 占位不用);不足 n-1 条时 G_d 必然不连通,
    # 这种 d 连并查集都不用建,先用 O(w log w) 的调和级数前缀把它筛掉
    avail = [0] + [sum(weight_count.get(k, 0) for k in range(d, maxw + 1, d))
                   for d in range(1, maxw + 1)]

    ans = 1
    for d in range(1, maxw + 1):
        enough_edges = avail[d] >= n - 1
        if enough_edges and spans(n, buckets, d, maxw):
            ans = lcm(ans, d)  # G_d 连通 ⇔ d 整除某棵生成树的边权 gcd
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 17:50
 * update_at: 2026-10-07 17:50
 */
// 1713 生成树:所有生成树的"边权 gcd"的 lcm。
//
// 关键结论:记 D = { d >= 1 : 只保留权值能被 d 整除的边后图连通 },则答案 = lcm(D)。
//   任取生成树 T,g = gcd(T) 整除 T 的每条边,故 T 全部落在 G_g 里,G_g 连通,g ∈ D;
//   反过来 d ∈ D 时取 G_d 的生成树 T,有 d | gcd(T)。两边取 lcm 即得相等。
// 于是只需对 d = 1..maxW 判一次连通性,连通就 ans = lcm(ans, d)。
//
// 复杂度:每个 d 重置一次并查集 O(N),共 O(N * maxW);并查集合并次数为 Σ_e τ(w_e)
// (τ 为约数个数,1e5 条边 × 平均约 10 个约数)。N <= 1000、maxW <= 32767 时约 4e7 次
// 基本操作,1s 内安全。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull; // 答案上界为 2^64-1(样例 9 已超过 2^63-1),必须无符号

const int MAXN = 1005;
const int MAXM = 100005;
const int MAXW = 32770; // 2^15 - 1 = 32767,权值桶数组开大一点

struct Edge {
    int u, v, w;
};

int n, m;
Edge e[MAXM];      // 全部边,按权值升序排序后存放
int cnt[MAXW];     // cnt[w] = 权值恰为 w 的边数
int st[MAXW];      // 权值 w 的边在排序后数组中的起始下标

int par[MAXN];     // 并查集:父指针
int sz[MAXN];      // 并查集:按大小合并用的集合大小

void dsu_init() {
    for (int i = 1; i <= n; ++i) {
        par[i] = i;
        sz[i] = 1;
    }
}

int find_root(int x) {
    while (par[x] != x) {
        par[x] = par[par[x]]; // 路径减半
        x = par[x];
    }
    return x;
}

// 合并两个集合,返回是否真的合并(即是否减少了一个连通块)
bool unite(int a, int b) {
    a = find_root(a);
    b = find_root(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) {
        int t = a;
        a = b;
        b = t;
    }
    par[b] = a;
    sz[a] += sz[b];
    return true;
}

ull gcd_ull(ull a, ull b) {
    while (b) {
        ull t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// 每个中间 lcm 都整除最终答案,所以 a / gcd(a, b) * b 不会中途溢出
ull lcm_ull(ull a, ull b) {
    return a / gcd_ull(a, b) * b;
}

bool cmp_w(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

int main() {
    scanf("%d %d", &n, &m);
    int maxW = 0;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
        ++cnt[e[i].w];
        if (e[i].w > maxW) maxW = e[i].w;
    }

    // n = 1(此时必然 m = 0)只有唯一的空生成树,约定答案为 1
    if (n <= 1 || maxW == 0) {
        printf("1\n");
        return 0;
    }

    // 按权值分桶:排序后 cnt/st 即可把"权值为 k 的边"定位成一段连续区间
    sort(e, e + m, cmp_w);
    st[0] = 0;
    for (int w = 0; w < maxW; ++w) {
        st[w + 1] = st[w] + cnt[w];
    }

    ull ans = 1;
    for (int d = 1; d <= maxW; ++d) {
        // d 的倍数里一条边都没有时 G_d 必不连通,先跳过,省掉一次并查集重置
        bool any = false;
        for (int k = d; k <= maxW; k += d) {
            if (cnt[k]) {
                any = true;
                break;
            }
        }
        if (!any) continue;

        dsu_init();
        int comp = n; // 当前连通块个数
        for (int k = d; k <= maxW && comp > 1; k += d) {
            for (int i = st[k]; i < st[k] + cnt[k]; ++i) {
                if (unite(e[i].u, e[i].v)) --comp;
            }
        }
        if (comp == 1) ans = lcm_ull(ans, (ull)d); // G_d 连通 ⇔ d ∈ D
    }

    printf("%llu\n", ans);
    return 0;
}

复杂度

  • 时间:并查集重置 O(N)O(N) 次共 O(N⋅wmax⁡)O(N \cdot w_{\max});并查集合并次数为 ∑eτ(de)≈M⋅10\sum_e \tau(d_e) \approx M \cdot 10,每次均摊 O(α)O(\alpha);再加上筛"该 dd 有没有边" 的 O(wmax⁡log⁡wmax⁡)O(w_{\max} \log w_{\max}) 调和级数代价。总计约 4×1074 \times 10^7 次基本操作, 实测最大数据点(N=1000N = 1000、M=100000M = 100000)在 1 s 限时内安全。
  • 空间:边表 O(M)O(M),分桶数组 O(N+wmax⁡)O(N + w_{\max}),并查集 O(N)O(N),共 O(N+M+wmax⁡)O(N + M + w_{\max})。

Python 版同一算法:主循环仍是枚举 dd + 并查集,只是额外用调和级数前缀 avail[d](dd 的倍数权值上的边数)先筛掉边数不足 N−1N - 1 的 dd,省下大量建表。 CPython 实测最大数据点约 0.7 s,在 1 s 限时上属于贴线状态,提交 Python 有 TLE 风险; 本题的正式解法以 C++ 版为准(最大点 0.04 s)。

总结

本题是"gcd⁡\gcd/lcm\mathrm{lcm} 与图连通性对偶"的模板题,和「矩阵树定理 + 莫比乌斯反演」 一族题目同源,但本题只问存在性、不问计数,所以反演被一句连通性判定取代了。核心两步:

  1. 换视角:不枚举指数级的生成树,而是枚举 dd,把"∃T\exists T 使 d∣g(T)d \mid g(T)" 等价成"GdG_d 连通",得到一个 O(wmax⁡)O(w_{\max}) 项的集合 DD;
  2. 取对偶:lcmTgcd⁡(T)=lcm⁡d∈Dd\mathrm{lcm}_T \gcd(T) = \operatorname*{lcm}_{d \in D} d, 两边分别由"g(T)∣Lg(T) \mid L"和"d∣g(Td)d \mid g(T_d)"给出,都是整除链上的直接结论。

实现上真正省时间的是按权值分桶:把 O(Mwmax⁡)O(M w_{\max}) 的暴力扫边降到 ∑eτ(de)\sum_e \tau(d_e),而 τ\tau 在 2152^{15} 内平均只有十来个。另外两个容易踩的坑是 答案要开无符号 64 位、以及 dd 只枚举到最大边权。

关于本题素材的两点说明(如实注明):

  • 本题的测试数据由素材源里的 data.py 用 cyaron 自造(分层生成:M=N−1M = N - 1、 M=NM = N、边权全为 22 的幂、以及两组大随机),题面则来自《信息学奥赛一本通 · 高手训练篇》的重建,因此数据未必覆盖官方原题的全部强度,本页结论以题面与 本地数据为准。
  • 素材源的 std.cpp 与题面一致(同一套算法),已编译跑通全部 10 个数据点并与 .out 逐点比对通过;另用"枚举全部生成树求 lcm\mathrm{lcm}"的暴力解在 N⩽6N \leqslant 6 的小图上 固定种子对拍通过,故本页按题面自研的实现与素材源结论一致,未发现 std 与题面不符的情况。