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}$

输出格式

输出答案。

3
1 2 10
2 3 20

50

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

76

提示

$2 \leq N \leq 10^5$ $1 \leq u_i, v_i \leq N$ $1 \leq w_i \leq 10^7$ 给定的图是一棵树。 输入中的所有数值均为整数。我们有 $f(1, 2) = 10$, $f(2, 3) = 20$, 且 $f(1, 3) = 20$, 因此我们应当输出它们的和，即 $50$.

标签: AtCoder|abc214D

来源

AtCoder|abc214D