分数: 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}
输出
打印答案。
示例输入 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