/ Vijos / 题库 /

宿命的PSS

宿命的PSS

背景

P.S.S:“我来自哪里?”
WH:“你来自一个图。”
P.S.S:“我是谁?”
WH:“你是最小生成树。”
P.S.S:“我又要到哪里去?”
WH:“你要成为一个最小完全图(边权之和最小的完全图)。”
P.S.S:“为……为什么啊?”
WH:“这是你的宿命!因为你无聊!!!P.S.S!”

描述

最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因,把这件事交给了你。

PS: 可以保证,这个最小生成树对于最后求出的完全图是唯一的。

格式

输入格式

输入的第一行是一个整数n,表示生成树的节点数。

接下来有n-1行,每行有三个正整数,依次表示每条边的端点编号和边权。

(顶点的边号在1-n之间,边权<maxint)

输出格式

一个整数ans,表示以该树为最小生成树的最小完全图的边权之和。

样例1

样例输入1

3 
1 2 4 
2 3 7

样例输出1

19

样例2

样例输入2

4
1 2 1
1 3 1
1 4 2

样例输出2

12

限制

每个测点1s

提示

n<20000

来源

冰尘e溶化邀请赛第四题,吴豪原创题。

信息

ID
1579
难度
5
分类
树结构 | 生成树 点击显示
标签
(无)
递交数
1340
已通过
451
通过率
34%
被复制
2
上传者