Skip to content

11137: 【原1137】唯一生成树

题目

题目描述

author: 陈皓 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1137

Description

wg是个爱思考的好孩子,当他学完最小生成树以后,他发现,一个图的最小生成树并不一定唯一(这都被你发现了 - -…)

于是他望着自己画出的最小生成树在想:“如何把它补成一个完全图,使这棵树是图的唯一的最小生成树”

随意补当然很简单了,wg 想知道的是使图的边权之和最小的方法(加入的边权值都必须是整数)

Input Format

第一行是一个整数t,表示数据组数

每组数据的第一行是一个整数n

接下来n-1 行,每行三个整数,u,v,w,表示u、v 之间有一条权值为w的边

Output Format

t行,每行一个整数,表示完全图的边权之和

Sample Input

1
3
1 2 4
2 3 7

Sample Output

19

数据规模

30%的数据中, n ≤ 1000

100%的数据中,t ≤ 20, 1 ≤ n ≤ 15000

1 ≤ u、v ≤ n, w ≤ 10000

保证数据合法

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!