UOJ Logo

NOI.AC

1S 512MB

#132. B君的第三题

统计

【题目描述】

大学四年,我为什么,为什么不好好读书,没找到和你一样的工作。

B 君某天看到了这样一个题,勾起了无穷的回忆。

输入 $n, k$ 和一棵 $n$ 个点的树,有边权,没有点权。两点 i, j 之间的距离$ D(i, j)$ 定义为路径上的边权和。求

$$\sum_{1 \le i < j \le n } \lceil \frac {D(i,j)} {k} \rceil $$

换句话说,枚举无序的两个点,求出距离除以 $k$ 上取整的和。

【输入格式】

输入第一行包含两个整数 n, k。

接下来 n − 1 行,每行三个整数 $x, y, z$,表示 $x$ 和 $y$ 之间有一条边,边权为 z。

【输出格式】

输出一行一个整数,表示答案。

【样例输入】

4    6    
1    2    2
1    3    3
1    4    4

【样例输出】

7

【数据规模与约定】

对于 100% 的数据,满足 $1 ≤ n ≤ 100000, 1 ≤ k ≤ 10$。

对于 100% 的数据,满足 $1 ≤ x, y ≤ n, 1 ≤ z ≤ 10$。

对于 30% 的数据,满足 $n ≤ 1000$。

对于另 20% 的数据,满足 $k = 1$。

对于另 20% 的数据,满足 $k = 2$。