D140 【最小生成树】构造完全图 走廊泼水节
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
0x60图论（0x62 最小生成树）例题1：走廊泼水节
P10928 走廊泼水节
题目描述
给定一棵 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。
求增加的边的权值总和最小是多少。
注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。
输入格式
第一行包含整数 。
接下来 行，每行三个整数 ，表示 节点与 节点之间存在一条边，长度为 。
输出格式
输出一个整数，表示权值总和最小值。
输入输出样例 #1
输入 #1
4
1 2 1
1 3 1
1 4 2
输出 #1
12
样例解释
添加 即可。
【数据范围与提示】
对于 的数据，；
对于 的数据，；
对于 的数据，。
提高8.16-18（并查集+最小生成树）
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 17
- 开始于
- 2024-8-1 22:00
- 结束于
- 2024-8-20 2:00
- 持续时间
- 436 小时
- 主持人
-
admin
- 参赛人数
- 14