J11 习题-4 求树上和

题目描述

给定一棵有 $N$ 个节点的数，节点的编号依次为 $1,2,\ldots,N$ 。

树上的第 $i$ 条边连接 $u_i,v_i$ ，权值为 $w_i$ 。定义 $f(u,v)$ 为从节点 $u$ 到达节点 $v$ 的最短路径上最大边权的值。

求 $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N f(i,j)$ 。

输入格式

共 $N$ 行： 第一行一个整数 $N$ ，表示树上节点的数量； 接下来的 $N-1$ 行，每行三个整数 $u_i,v_i,w_i$ ，依次表示每条边连接的节点编号和边权。

输出格式

一行一个整数，按题意输出。

样例输入1

3
1 2 10
2 3 20

样例输出1

50

样例1解析

$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

数据范围

对于 $100 \%$ 的数据：$2\leq N\leq 10^5,1\leq u_i,v_i\leq N,1\leq w_i\leq 10^7$ ，保证图是一棵树。