6922: 「一本通 3.1 练习 2」构造完全图
[Creator : ]
Description
对于完全图 $G$，若有且仅有一棵最小生成树为 $T$，则称完全图 $G$ 是树 $T$ 扩展出的。
给你一棵树 $T$，找出 $T$ 能扩展出的边权和最小的完全图 $G$。
给你一棵树 $T$，找出 $T$ 能扩展出的边权和最小的完全图 $G$。
Input
第一行 $N$ 表示树 $T$ 的点数；
接下来 $N-1$ 行三个整数 $S_i,T_i,D_i$；描述一条边 $(S_i,T_i)$ 权值为 $D_i$；
保证输入数据构成一棵树。
接下来 $N-1$ 行三个整数 $S_i,T_i,D_i$；描述一条边 $(S_i,T_i)$ 权值为 $D_i$；
保证输入数据构成一棵树。
Output
输出仅一个数，表示最小的完全图 $G$ 的边权和。
Constraints
对于 $20\%$ 的数据，$N \le 10$；
对于 $50\%$ 的数据，$N \le1,000$；
对于 $100\%$ 的数据，$N \le 10^5,\ 1 \le D_i \le10^5$。
对于 $50\%$ 的数据，$N \le1,000$；
对于 $100\%$ 的数据，$N \le 10^5,\ 1 \le D_i \le10^5$。
Sample 1 Input
4
1 2 1
1 3 1
1 4 2
Sample 1 Output
12
添加 D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。