题目描述

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

输出格式

请输出答案。

说明/提示

限制条件

• $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 翻译

数据范围与约定

第 $i$ 条边（$1 \leq i \leq N-1$）连接顶点 $u_i$ 和顶点 $v_i$，其权值为 $w_i$。

• $2 \leq N \leq 10^5$

• $1 \leq u_i, v_i \leq N$

• $1 \leq w_i \leq 10^7$

可见测试数据

输入数据 1

3
1 2 10
2 3 20

输出数据 1

50

输入数据 2

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

输出数据 2

76

输入数据 3

12
1 2 4914637
2 3 1451447
2 4 7605441
4 5 9898344
2 6 684166
4 7 2742597
4 8 5420733
5 9 1642938
4 10 660456
6 11 315940
3 12 8168668

输出数据 3

473341660