A5542 | $「一本通 3.1 练习 2」构造完全图$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

对于完全图 $G$，若有且仅有一棵最小生成树为 $T$，则称完全图 $G$ 是树 $T$ 扩展出的。 给你一棵树 $T$，找出 $T$ 能扩展出的边权和最小的完全图 $G$。

第一行 $N$ 表示树 $T$ 的点数； 接下来 $N-1$ 行三个整数 $S_i, T_i, D_i$；描述一条边 $(S_i, T_i)$ 权值为 $D_i$； 保证输入数据构成一棵树。

输出仅一个数，表示最小的完全图 $G$ 的边权和。

输入 #1

输出 #1

C++ 编辑器

输入

输出