← 返回题目列表

AtCoder · abc214_d

G. 最大重量总和

中文机器翻译题面 查看原题

分数: 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