1254: 最小生成完全图
题目
题目描述
对于完全图 $G$ ，若有且仅有一棵最小生成树为 $T$，则称完全图 $G$ 是树 $T$ 扩展出的。
给你一棵树 $T$ ，找出 $T$ 能扩展出的边权和最小的完全图 $G$ 。
输入格式
第一行一个正整数 $N$，表示树 $T$ 的节点个数
接下来 $N - 1$ 行，每行三个用空格隔开的整数 $S_i, T_i, D_i$，描述了一条连接 $S_i, T_i$ 且权值为 $D_i$ 的边
保证输入是一棵树
输出格式
输出仅一个数，表示最小生成完全图 $G$ 的边权和
样例输入
text
4
1 2 1
1 3 1
1 4 2
样例输出
text
12
样例解释
添加三条边，$D(2,3)=2, D(3,4)=3, D(2,4)=3$ 即可
数据范围
时间限制：1000 ms 空间限制：512 mb
无捆绑测试
- $(\text{20 points})~ N \leq 10$
- $(\text{30 points})~ N \leq 10^3$
- $(\text{50 points})~ N\leq 10^5, 1\leq D_i \leq 10^5$
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！