传统题 1000ms 256MiB

Accumulation Degree

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Accumulation Degree

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

After days of heavy rain, FJNU was flooded into an undirected tree with nn nodes numbered from 11 to nn. The rain also formed ponds on the road making it difficult to walk. More precisely, there are n1n-1 roads in this tree, the ii-th (1in1)(1 \leq i \leq n-1) edge connects node uiu_i and node viv_i and it has a weight wiw_i means there is ponding with degree wiw_i on this road.

Liu Wei, the clever Peppa Pig was forced by Tai Liang to calculate the accumulation degree of this tree:

For different node uu and vv, let f(u,v)f(u,v) be the greatest weight edge in the shortest path from node uu to node vv.

Liu Wei needs to calculate i=1n1j=i+1nf(i,j)\sum^{n-1}_{i=1}\sum^{n}_{j=i+1}f(i,j).

As a full stack developer, Liu Wei has more important things to do, so you are asked to help him solve this problem.

Input

The first line contains one integers n(2n105)n(2\leq n\leq 10^5).

In the following n1n-1 lines, each line contains three integers $u_i,v_i,w_i(1 \leq u_i,v_i \leq N,1 \leq w_i \leq 10^7)$ denoting there is an edge between node uiu_i and viv_i with a weight wiw_i.

Output

Print a single integer, denoting the answer to the question.

3
1 2 10
2 3 20
50

福建师范大学第十九届程序设计竞赛重现赛

未参加
状态
已结束
规则
IOI
题目
13
开始于
2022-5-21 6:30
结束于
2023-4-19 14:30
持续时间
8000 小时
主持人
参赛人数
32