形式化题目

给定一棵 $n$ 个点的带权树 $T$（$n-1$ 条边，边权为正整数）。求边权和最小的完全图 $G$（$n$ 个点，每对点之间恰有一条边），使得 $G$ 的最小生成树有且仅有 $T$ 一棵，并输出这个最小边权和。

注意两点：$T$ 必须是 $G$ 的生成树，所以树边原样进入 $G$、权值不可改；不确定的只有 $\binom{n}{2} - (n-1)$ 条非树点对之间的补边，问题就是给它们各定一个最小的合法权值。

样例 $n = 4$，树边 $(1,2)$ 权 1、$(1,3)$ 权 1、$(1,4)$ 权 2。下图中实线为树边，虚线为需要补的边及其权值：

graph LR
    N1["点 1"] ---|"1"| N2["点 2"]
    N1 ---|"1"| N3["点 3"]
    N1 ---|"2"| N4["点 4"]
    N2 -.->|"补 2"| N3
    N3 -.->|"补 3"| N4
    N2 -.->|"补 3"| N4

输出 $12$：树边和 $1 + 1 + 2 = 4$，补边 $2 + 3 + 3 = 8$。细心观察补边的取值——$(2,3)$ 在树上的路径 $2 \to 1 \to 3$ 最大边权是 1，补边取 $1 + 1 = 2$；$(2,4)$、$(3,4)$ 的路径最大边权都是 2，补边取 $2 + 1 = 3$。这个"$+1$"正是全题的关键。

正解

思路

朴素做法及其瓶颈。 最直接的思路：枚举每个非树点对 $(u,v)$，用 LCA/倍增求出路径最大边权 $M(u,v)$，给补边赋一个合法权值后求和。每次查询 $O(\log n)$，总复杂度 $O(n^2 \log n)$——$n = 10^5$ 时点对有约 $5 \times 10^9$ 个，查询再快也无济于事。瓶颈是点对本身有 $O(n^2)$ 个，必须从"逐点对"改成"按边批量计数"。

观察一：补边权的下界是 $M + 1$。 设非树点对 $(u,v)$ 的路径最大边权为 $M$，给这条补边赋权 $w$：

• $w < M$：把该边加入 $T$ 形成环、删掉环上最大边，得到比 $T$ 更小的生成树，$T$ 根本不是 MST；
• $w = M$：同样换边得到等权的另一棵生成树，MST 不唯一，违反"有且仅有"；
• $w > M$：按 Kruskal 的顺序，处理到这条边时它的路径上所有边（权都 $\leqslant M$）已把两端连通，它永远不会入树——所以 Kruskal 输出的就是 $T$，$T$ 是 MST。

唯一性也由严格大于保证：任取另一棵生成树 $T'' \neq T$，它必含某条补边 $e$（两棵树都是 $n-1$ 条边）；删去 $T''$ 中的 $e$ 会把点集分成两块，而 $e$ 在 $T$ 上的路径必然横跨这条割，取其中的跨割边 $f$——若 $f \in T''$，则 $T''$ 含两条跨割边、必然有环，故 $f \in T$ 且 $f \notin T''$；把 $T''$ 里的 $e$ 换成 $f$ 仍是生成树，且 $w(f) \leqslant M < w(e)$，权值严格下降。每换一次，$T''$ 就多一条 $T$ 的边，最多 $n-1$ 次必换成 $T$，沿途严格降权，故任何 $T'' \neq T$ 都严格重于 $T$，$T$ 是唯一 MST。

边权是整数，所以每条补边的最小合法权值就是 $M + 1$，且各条补边互相独立、逐对取下界即全局最优。于是

其中相邻点对的 $M$ 就是树边原权，第一项已把树边和算进去了。

观察二：把点对按边聚合成块。 一条树边对应一大批点对——"分居该边两侧"的点对，其路径最大边权至少是这条边。按边权升序做 Kruskal 式合并：权 $w$ 的边把大小 $a$、$b$ 的两个连通块并成一块时，跨两块的 $a \times b$ 个点对的路径必经过这条边（max $\geqslant w$）；而这些路径的其余部分由已处理的边组成——两端在块内连通只可能走已处理的边——权都不超过 $w$（max $\leqslant w$），所以这批点对的 $M$ 恰为 $w$，一次贡献 $w \cdot a \cdot b$。每个点对恰好在"路径上最晚处理的那条边"处被统计一次，不重不漏，$O(n)$ 次合并就累计完 $O(n^2)$ 个点对。

样例的合并与计数过程：

表中三行覆盖了全部 $\binom{4}{2} = 6$ 个点对，$\sum M = 9$；非树点对数 $\binom{4}{2} - 3 = 3$，故 $\text{ans} = 9 + 3 = 12$。对照逐对验证：非树补边 $2 + 3 + 3 = 8$，树边和 4，合计 12，与样例输出一致。

代码

pair_max_edge_sum() 实现观察二的合并计数（循环体 total += w * size[ru] * size[rv] 就是 $w \cdot a \cdot b$），solve() 负责读入、按权排序，并用组合数闭式给每个非树点对补上 $+1$。

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#!/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-09-30 14:18
# update_at: 2026-09-30 14:18

import sys


def find(root: list[int], x: int) -> int:
    """并查集查根：路径压缩后返回 x 所在连通块的代表点。"""
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


def pair_max_edge_sum(n: int, edges: list[tuple[int, int, int]]) -> int:
    """按边权升序合并连通块，求所有点对之间树上路径的最大边权之和。

    合并时跨两块的点对路径必经过当前边，且块内边权都不超过它，
    所以这批点对的"路径最大边权"恰为这条边的权值。
    """
    root = list(range(n + 1))  # 父点表，下标 0 不用（点编号从 1 开始）
    size = [1] * (n + 1)
    total = 0
    for u, v, w in edges:
        ru, rv = find(root, u), find(root, v)
        total += w * size[ru] * size[rv]  # 跨块点对数 = 两块大小之积
        root[ru] = rv
        size[rv] += size[ru]
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    edges = [(next(data), next(data), next(data)) for _ in range(n - 1)]  # 依次读入 u、v、w
    edges.sort(key=lambda e: e[2])  # 按边权升序，即 Kruskal 的合并顺序

    # 全部点对的路径最大边权之和（树边已按原权计入），再给每个非树点对补 +1
    ans = pair_max_edge_sum(n, edges) + n * (n - 1) // 2 - (n - 1)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * 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-05 04:05
 * update_at: 2026-10-05 04:05
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

typedef long long ll;

struct Edge {
    ll u;
    ll v;
    ll w;
};

ll n;
Edge edges[MAXN]; // 树的 n-1 条边，读入后按边权升序排序
ll root[MAXN];    // 并查集父点表，下标 0 不用（点编号从 1 开始）
ll size_of[MAXN]; // 块大小：合并时跨两块点对数 = 两块大小之积

// 并查集查根，带路径压缩。
ll find_root(ll x) {
    while (root[x] != x) {
        root[x] = root[root[x]];
        x = root[x];
    }
    return x;
}

// 按边权升序合并连通块，累计所有点对树上路径最大边权之和。
// 合并权为 w 的边时，跨两块的 a*b 个点对路径必经过这条边，
// 且块内已用边权都不超过 w，所以这批点对的路径最大边权恰为 w。
ll pair_max_edge_sum() {
    ll total = 0;
    for (ll i = 1; i <= n - 1; i++) {
        ll ru = find_root(edges[i].u);
        ll rv = find_root(edges[i].v);
        total += edges[i].w * size_of[ru] * size_of[rv];
        root[ru] = rv;
        size_of[rv] += size_of[ru];
    }
    return total;
}

bool cmp_edge(Edge a, Edge b) {
    return a.w < b.w;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (ll i = 1; i <= n - 1; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    for (ll i = 1; i <= n; i++) {
        root[i] = i;
        size_of[i] = 1;
    }
    sort(edges + 1, edges + n, cmp_edge); // 按边权升序，即 Kruskal 的合并顺序

    // 每条非树点对的补边最小取"路径最大边权 + 1"，非树点对共 C(n,2) - (n-1) 个
    ll ans = pair_max_edge_sum() + n * (n - 1) / 2 - (n - 1);
    cout << ans << "\n";

    return 0;
}

复杂度

• 时间：排序 $O(n \log n)$，并查集（路径压缩）$O(n \,\alpha(n))$，总计 $O(n \log n)$，与同算法的 C++ 正解同阶。
• 空间：$O(n)$，存边、父点表和块大小各一份。
• 答案最大约 $2.5 \times 10^{14}$，Python int 自动支持大整数；本地实测最大点 0.099s、峰值 55.6MB，对 1000ms / 128MB 的限制留有余量。

总结

1. 唯一 MST 的充要条件：每条非树边权严格大于它两端点在 $T$ 上的路径最大边权；整数权下补边最小取 $M + 1$。
2. 目标拆成两块：$\sum M$（含树边和）+ 非树点对数，后者是组合数闭式。
3. $\sum M$ 不逐点对求，而是按边权升序并查集合并，用"块大小乘积 $\times$ 边权"批量累计——把 $O(n^2)$ 的点对枚举压成 $O(n)$ 次合并，整体 $O(n \log n)$。