AT_abc214_d [ABC214D] Sum of Maximum Weights

题目描述

有一棵包含 $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}$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 2 10
2 3 20

输出 #1

50

输入输出样例 #2

输入 #2

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

输出 #2

76

说明/提示

限制条件

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

样例解释 1

$f(1, 2) = 10,\ f(2, 3) = 20,\ f(1, 3) = 20$，因此它们的和为 $50$，输出 $50$。

由 ChatGPT 4.1 翻译