D - 最大权重之和

得分：400分

问题描述

我们有一个有$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)$。

约束

• $2 \leq N \leq 10^5$
• $1 \leq u_i, v_i \leq N$
• $1 \leq w_i \leq 10^7$
• 给定的图是一棵树。
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入中给出:

$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