Transfer Speeds Sum

题目描述

一个计算机网络有 n 台计算机和 n-1 条连接。通过这些连接，每对计算机之间都可以交换信息。 每条连接都有一个传输速率。令 d(a,b) 表示计算机 a 和 b 之间的传输速率，它等于连接 a 和 b 之间路径上速度最小的连接的速率。你的任务是计算所有计算机对之间传输速率的总和。

输入格式

第一行包含整数 n：计算机的数量。计算机编号为 1,2,$\dots$,n。 接下来有 n-1 行，每行描述一条连接。每行包含三个整数 a、b 和 x：存在一条连接在计算机 a 和 b 之间，传输速率为 x。

输出格式

输出一个整数：传输速率的总和。

4
1 2 5
2 3 1
2 4 2

12

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x \le 10^6$ 样例解释：下图对应样例输入：

标签: CSES3111|高级图论问题

来源

CSES3111|高级图论问题