/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
N 頂点の木があり、頂点は 1, 2, \dots, N と番号付けられています。
i \, (1 \leq i \leq N - 1) 番目の辺は頂点 u_i と頂点 v_i を結び、重みは w_i です。
異なる頂点 u, v に対し、頂点 u から頂点 v までの最短パスに含まれる辺の重みの最大値を f(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
Score : 400 points
Problem Statement
We have a tree with N vertices numbered 1, 2, \dots, N.
The i-th edge (1 \leq i \leq N - 1) connects Vertex u_i and Vertex v_i and has a weight w_i.
For different vertices u and v, let f(u, v) be the greatest weight of an edge contained in the shortest path from Vertex u to Vertex v.
Find \displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j).
Constraints
- 2 \leq N \leq 10^5
- 1 \leq u_i, v_i \leq N
- 1 \leq w_i \leq 10^7
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
u_1 v_1 w_1
\vdots
u_{N - 1} v_{N - 1} w_{N - 1}
Output
Print the answer.
Sample Input 1
3 1 2 10 2 3 20
Sample Output 1
50
We have f(1, 2) = 10, f(2, 3) = 20, and f(1, 3) = 20, so we should print their sum, or 50.
Sample Input 2
5 1 2 1 2 3 2 4 2 5 3 5 14
Sample Output 2
76