形式化题目

给定一棵 $n$ 个节点的树 $T=(V,E,w)$，树边权值为整数。要求给每个非树点对 $(u,v)$ 填上一个整数权值，把 $T$ 扩充成完全图 $K_n$（原树边权值保持不变），使得 $T$ 仍然是 $K_n$ 的唯一最小生成树，并让所有新增边的权值之和最小。

正解

思路

先算一条非树边能取多小

目标是「新增边权之和」，而「$T$ 是唯一 MST」是逐边的局部条件：它只约束每条非树边 与树上路径的关系，不同非树边之间没有耦合。所以可以单独求每条非树边的最小合法权值， 再全部相加。

设 $M_{uv}$ 为 $T$ 上 $u\to v$ 路径的最大树边权。这条边最小只能填 $M_{uv}+1$：

• 填 $c<M_{uv}$：把路径上权值为 $M_{uv}$ 的树边记为 $f$。在 $T$ 中加入 $(u,v)$、 删去 $f$ 得到另一棵生成树，权值为 $w(T)-M_{uv}+c<w(T)$，与 $T$ 是最小生成树矛盾。
• 填 $c=M_{uv}$：同样的替换得到一棵权值相等的生成树 $T'\neq T$，与 $T$ 是唯一 MST 矛盾。
• 填 $c=M_{uv}+1$：任取 $T'\neq T$ 与 $e=(u,v)\in T'\setminus T$。$T$ 上加 $e$ 形成唯一圈，圈上必有一条树边 $f$ 不在 $T'$ 中（否则 $T'$ 里 $u,v$ 已连通，$e$ 会成圈）， 于是 $c(e)=M_{uv}+1>w(f)$，用 $f$ 换掉 $e$ 使 $T'$ 权值严格减小。所以任何 $T'\neq T$ 都不是最小生成树，$T$ 唯一。

也就是：$T$ 是唯一 MST，等价于每条非树边都严格大于它对应路径的最大树边权。

卡点：$O(n^2)$ 条非树边的枚举跑不完

按这个结论，只要对每条非树边求一次「路径最大边权」即可。但非树边有 $\binom{n}{2}-(n-1)$ 条，$n=6000$ 时约 $1.8\times 10^7$ 条；即便每次查询 $O(1)$， Python 也跑不完。真正的瓶颈不是「求路径最值」，而是「先把所有非树边枚举出来」。

关键观察：路径最大边权 = 首次连通时的树边权值

把 Kruskal 的过程看成在按权值递增接受树边。当 $u,v$ 在某一步第一次被连通时， 那条让它们连通的树边就是路径 $P_{uv}$ 上的最大边——因为 Kruskal 按非降序处理， 在此之前 $u,v$ 不连通，之后出现的树边权值都不会更小。

于是不要枚举非树边，改去枚举合并事件：合并事件只有 $n-1$ 个，每个事件一次性 处理它负责的一整批非树边。

批量定价

设当前处理权值为 $w$ 的树边 $(x,y)$，$A$、$B$ 是两端所在的连通块。此时 $A\times B$ 点对中：

• 有 $a\cdot b$ 个点对，其中 $a=|A|$、$b=|B|$；
• 其中恰好一个是刚被接受的树边 $(x,y)$ 本身；
• 剩下 $a\cdot b-1$ 个都是非树边，且它们的 $M_{uv}$ 恰好等于 $w$。

所以每条填 $w+1$，本步贡献 $(a\cdot b-1)\cdot(w+1)$。每条非树边归属的「首次连通事件」 唯一，故不重不漏。下面的表把题面两组样例各跑一遍，最后一格就是输出。

每行是一次 Kruskal 合并：先给出这次连接的两块大小，再给出这批非树边的条数与单价。 第一组样例只有第 2 步有贡献——补上唯一的非树边 $(2,3)$，权值 $3+1=4$。 第二组样例是一条链，第 3 步一次要定价 $(1,4)$ 和 $(2,4)$ 两条非树边，各填 $5+1=6$， 合计 $12$，累计 $5+12=17$，与题面输出一致。要注意读 $a\cdot b$ 时必须读合并前的 块大小，合并之后这个划分就消失了。

第一组样例补完后的完全图如下：原树边是 $(1,2)$ 权 2、$(1,3)$ 权 3，唯一的非树边 $(2,3)$ 被填成 $3+1=4$。

flowchart LR
  n1(("1"))
  n2(("2"))
  n3(("3"))
  n1 ---|"2 原树边"| n2
  n1 ---|"3 原树边"| n3
  n2 ---|"4 新增边"| n3

观察重点是 $(2,3)$ 的权值：它与「第二次合并时那条树边 $(1,3)$ 的权值 $3$」相差正好 1。 如果把它填成 $3$，则 $\{(1,2),(2,3)\}$ 与 $\{(1,2),(1,3)\}$ 都是权值 5 的生成树， 唯一性被破坏；填成 4 之后，任何非树生成树都会比原树更重。

实现要点

• 并查集除 parent 外维护每个根的 size，合并时小树挂大树，保证近 $O(\alpha(n))$。
• 边存成 (weight, x, y) 元组，sorted 直接给出 Kruskal 顺序，不需要额外的 key=。
• 累加必须在合并之前完成，否则读到的块大小已经被改掉。

代码

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
75
76
77
78
79
80
81
82
83
84
85/**
 * 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-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 秘密的牛奶运输：按 Kruskal 顺序累加“补全完全图”所需的最小新增边权
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 500005;

int parent[MAXN];
ll sz[MAXN]; // 只有根节点的 size 有意义

int find_root(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

struct Edge { // 树边：权值放首位便于排序
    ll w;
    int x;
    int y;
};

bool cmp(const Edge& a, const Edge& b) {
    if (a.w != b.w) {
        return a.w < b.w;
    }
    if (a.x != b.x) {
        return a.x < b.x; // 与 Python 元组排序的并列处理保持一致
    }
    return a.y < b.y;
}

int main() {
    int cases;
    if (scanf("%d", &cases) != 1) {
        return 0;
    }
    for (int tc = 0; tc < cases; tc++) {
        int n;
        scanf("%d", &n);
        vector<Edge> edges(n > 1 ? n - 1 : 0);
        for (int i = 0; i + 1 < n; i++) {
            int x, y;
            ll w;
            scanf("%d %d %lld", &x, &y, &w);
            edges[i].w = w;
            edges[i].x = x;
            edges[i].y = y;
        }
        sort(edges.begin(), edges.end(), cmp);

        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
        ll total = 0;
        for (int i = 0; i < (int)edges.size(); i++) {
            int rx = find_root(edges[i].x), ry = find_root(edges[i].y);
            // 这两块之间除这条树边外的点对，每条最小可行权值都是 w+1
            total += (sz[rx] * sz[ry] - 1) * (edges[i].w + 1);
            if (sz[rx] < sz[ry]) { // 按大小合并
                int t = rx;
                rx = ry;
                ry = t;
            }
            parent[ry] = rx;
            sz[rx] += sz[ry];
        }
        printf("%lld\n", total);
    }
    return 0;
}

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#!/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-01 23:58
# update_at: 2026-10-02 00:03

import sys


def find(parent: list[int], x: int) -> int:
    """路径减半地找 x 所在并查集的根，顺带把沿途节点挂向祖父。"""
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x


def minimum_added_weight(n: int, tree_edges: list[tuple[int, int, int]]) -> int:
    """补成完全图且原树仍是唯一 MST 时，新加边权和的最小值。

    按 Kruskal 的顺序（权值递增）接受树边：轮到权值 w 的边 (x,y) 时，两端点所在的
    连通块 A、B 内部的边已经被全部定好，此刻两个块之间唯一确定还存在的是这条树边。
    要让原树保持唯一 MST，A×B 里其余 |A|·|B|-1 条边的最小可行权值就是 w+1：
    取 w 会让它们与该树边并列（MST 不唯一），取更小则原树不再是 MST。
    """
    parent = list(range(n + 1))
    size = [1] * (n + 1)                       # 只有根节点的 size 有意义
    total = 0
    for weight, x, y in sorted(tree_edges):
        root_x, root_y = find(parent, x), find(parent, y)
        # 这两块之间除这条树边外的点对，路径最大树边权都是 weight，所以每条填 weight+1
        added = (size[root_x] * size[root_y] - 1) * (weight + 1)
        total += added
        if size[root_x] < size[root_y]:        # 按大小合并，控制树的深度
            root_x, root_y = root_y, root_x
        parent[root_y] = root_x
        size[root_x] += size[root_y]
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    test_count = next(data)

    for _ in range(test_count):
        n = next(data)
        tree_edges: list[tuple[int, int, int]] = []
        for _ in range(n - 1):
            x, y, weight = next(data), next(data), next(data)
            tree_edges.append((weight, x, y))  # 权值放首位，交给 sorted 排 Kruskal 序
        out.append(str(minimum_added_weight(n, tree_edges)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(n\log n)$ 每组，其中排序 $O(n\log n)$、并查集 $O(n\,\alpha(n))$。 相比枚举全部非树边的 $O(n^2)$ 做法有本质提升；$n=6000$ 时实测约 0.03s。
• 空间复杂度：$O(n)$，即并查集两个数组与边列表。

总结

• 目标函数可拆时，先求「每条非树边单独的最小合法权值」，再把各边的局部下界相加。
• $T$ 是唯一 MST 的充要条件：每条非树边严格大于其树上路径的最大边权。
• 把「路径最大边权」换成 Kruskal 的视角，它就成了「两点首次连通时那条边的权值」； 于是 $O(n^2)$ 条非树边的枚举被压成 $n-1$ 次合并事件，每次 $O(1)$ 批量定价。
• 并查集按大小合并，既控制树高，又让批量定价所需的「两块大小」随手可得。