问题 4009 --2.构造完全图

4009: 2.构造完全图

题目描述

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

输入

第一行N表示树T的点数。
接下来N-1行： Si， Ti， Di；描述一条边（ Si,Ti）权值为 Di。
保证输入数据构成一棵树。

输出

一个数，表示最小的图G的边权和。

样例输入输出

输入#1 复制 
4
1 2 1
1 3 1
1 4 2
输出#1 复制 
12

提示

添加D(2,3)=2,D(3,4)=3,D(2,4)=3即可。
【 数据范围】
对于20%的数据， N<=10
对于50%的数据， N<=1000
对于100%的数据， N<=100000， 1<=Di<=100000

发表题解
序号 标题 作者 发表时间 费用 订购数 操作

题目信息

提交
难度
提高+/省选-
标签
点击显示
递交数
11
已通过
9
通过率
82%
时间限制
1 秒
内存限制
128 MB
来源
一本通(提高篇)
收藏