← 返回题目列表

AtCoder · ddcc_2016_qual_d

D. 道路网络

中文机器翻译题面 查看原题

配点 : 1200 点

問題文

N 城市和 有一个国家由 N-1 道路组成。在每个城市 它的编号为 1, \, 2, \, … \, , \, N 。 i(1 ≦ i ≦ N-1) 第二条路是市区 A_i 和城市 B_i 是长度 它与 C_i 连接。 道路是双向的,城市可以通过多条道路相互旅行。

有一天, 满足1≦i<j≦N 满足 2 城市 i, \, j 关于城市 i 和城市 j 如果没有道路直接连接 直接连接的长度 i 和城市 j 执行了添加 X 道路的操作。

d(u, \, v) 城市 u 来自城市 作为到 v 的最短距离, 关于 1≦i<j≦N 满足 2 城市 i, \, j 计算每个 d(i, \, j) 并输出总和。

制約

  • 2 ≦ N ≦ 10^{5}
  • 1 ≦ A_i, \, B_i ≦ N(1 ≦ i ≦ N-1)
  • 1 ≦ C_i ≦ 10^{5}(1 ≦ i ≦ N-1)
  • 1 ≦ X ≦ 10^5
  • 在操作之前的某个时刻 2 可以沿着多条道路在两个城市之间行驶。
  • C_i, \, X 均为整数

入力

输入是按以下格式从标准输入给出的。

N X
A_1 B_1 C_{1}
.
.
.
A_{N-1} B_{N-1} C_{N-1}

出力

答案 1 行输出。


入力例 1

6 3
1 2 2
2 3 3
4 1 4
6 4 10
5 4 8

出力例 1

51

下图展示了城市和道路之间的关系。蓝色实线原本就在那里 N-1 黑色虚线是操作新添加的长度。 它代表 3 的路径。

9461ca7dead16c099ef63ac3b181699f.png

入力例 2

20 68
12 10 34
12 14 35
12 9 15
17 9 37
1 17 47
1 2 12
11 2 7
11 15 32
13 11 15
13 4 2
5 1 35
20 5 51
3 4 39
16 11 21
3 18 70
17 8 68
20 7 2
6 3 34
19 2 5

出力例 2

11278