102143: [AtCoder]ABC214 D - Sum of Maximum Weights

Problem Statement

We have a tree with $N$ vertices numbered $1, 2, \dots, N$.
The $i$-th edge $(1 \leq i \leq N - 1)$ connects Vertex $u_i$ and Vertex $v_i$ and has a weight $w_i$.

For different vertices $u$ and $v$, let $f(u, v)$ be the greatest weight of an edge contained in the shortest path from Vertex $u$ to Vertex $v$.

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

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq u_i, v_i \leq N$
• $1 \leq w_i \leq 10^7$
• The given graph is a tree.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

50

We have $f(1, 2) = 10$, $f(2, 3) = 20$, and $f(1, 3) = 20$, so we should print their sum, or $50$.

Sample Input 2

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

Sample Output 2

76

问题描述

我们有一个拥有$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}$

输出

打印答案。

样例输入1

3
1 2 10
2 3 20

样例输出1

50

我们有$f(1, 2) = 10$，$f(2, 3) = 20$，以及$f(1, 3) = 20$，所以我们应该打印它们的和，即$50$。

样例输入2

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

样例输出2

76