最大边权之和

题目描述

有一棵 $N$ 个顶点的树,顶点编号为 $1, 2, \dots, N$。

第 $i$ 条边($1 \leq i \leq N - 1$)连接顶点 $u_i$ 和顶点 $v_i$,权值为 $w_i$。

对于不同的顶点 $u$ 和 $v$,设 $f(u, v)$ 为从顶点 $u$ 到顶点 $v$ 的最短路径上所含边的权值的最大值。

求 $\displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j)$。

输入格式

输入按以下格式从标准输入给出：

$N$
$u_1$ $v_1$ $w_1$
$\vdots$
$u_{N - 1}$ $v_{N - 1}$ $w_{N - 1}$

输出格式

输出答案。

样例

3
1 2 10
2 3 20

50

有 $f(1, 2) = 10$、$f(2, 3) = 20$、$f(1, 3) = 20$,所以应输出它们的和,即 $50$。

5
1 2 1
2 3 2
4 2 5
3 5 14

76

数据范围

• $2 \le N \le 10^5$
• $1 \le u_i, v_i \le N$
• $1 \le w_i \le 10^7$
• 给定的图是一棵树
• 输入均为整数