AT_ddcc_2016_qual_d.道路網

有一个由 $N$ 个城市和 $N-1$ 条道路组成的国家。每个城市编号为 $1,\,2,\,\ldots,\,N$。第 $i$ 条道路（$1\leq i\leq N-1$）连接城市 $A_i$ 和城市 $B_i$，长度为 $C_i$。道路是双向通行的，任意两个城市之间都可以通过若干条道路互相到达。

有一天，对于所有满足 $1\leq i<j\leq N$ 的两个城市 $i$ 和 $j$，如果城市 $i$ 和城市 $j$ 之间没有直接相连的道路，则会新增一条长度为 $X$ 的直接道路连接城市 $i$ 和城市 $j$。

设 $d(u,\,v)$ 表示城市 $u$ 到城市 $v$ 的最短距离。请你计算所有满足 $1\leq i<j\leq N$ 的城市对 $(i,\,j)$ 的 $d(i,\,j)$ 之和，并输出结果。

输入通过标准输入按以下格式给出。

$N$ $X$ $A_1$ $B_1$ $C_1$ $\ldots$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$

请输出答案，输出一行。

限制条件

• $2\leq N\leq 10^{5}$
• $1\leq A_i,\,B_i\leq N\ (1\leq i\leq N-1)$
• $1\leq C_i\leq 10^{5}\ (1\leq i\leq N-1)$
• $1\leq X\leq 10^5$
• 在操作进行之前，任意两个城市之间都可以通过若干条道路互相到达
• $C_i,\,X$ 均为整数

样例说明 1

下图表示城市和道路的关系。蓝色实线表示原有的 $N-1$ 条道路，黑色虚线表示操作后新增的长度为 $3$ 的道路。

由 ChatGPT 4.1 翻译