← 返回题目列表

Codeforces · 771/C

C. 熊和树跳

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

树是没有环的无向连通图。两个顶点之间的距离是它们之间的简单路径中的边数。

Limak 是一只小北极熊。他生活在一棵由 n 个顶点组成的树中,编号为 1 到 n。

Limak 最近学会了如何跳跃。他最多可以从一个顶点跳到距离k以内的任何顶点。

对于一对顶点 (s, t),我们将 f(s, t) 定义为 Limak 需要从 s 到 t 的最小跳跃次数。您的任务是找到所有顶点对 (s, t) 上的 f(s, t) 之和,使得 s < t。

输入

输入的第一行包含两个整数 n 和 k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ 5)——分别是树中的顶点数和允许的最大跳跃距离。

接下来的 n - 1 行描述树中的边。这些行的第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n)——与第 i 条边连接的顶点的索引。

保证给定的边形成一棵树。

输出

打印一个整数,表示所有顶点对 (s, t) 上的 f(s, t) 之和,使得 s < t。

示例

输入 #1

6 2
1 2
1 3
2 4
2 5
4 6

输出 #1

20

输入 #2

13 3
1 2
3 2
4 2
5 2
3 6
10 6
6 7
6 13
5 8
5 9
9 11
11 12

输出 #2

114

输入 #3

3 5
2 1
3 1

输出 #3

3

注意

在第一个示例中,给定的树有 6 个顶点,如下图所示。 Limak 最多可以跳到距离 2 内的任何顶点。例如,从顶点 5 他可以跳到任意顶点:1、2 和 4(当然,他也可以跳到顶点 5 本身)。

有 $$\frac{n(n-1)}{2} = 15$$ 个顶点 (s, t) 对,使得 s < t。对于其中 5 对,Limak 需要两次跳跃:(1, 6)、(3, 4)、(3, 5)、(3, 6)、(5, 6)。对于其他 10 对,一跳就足够了。所以,答案是 5·2 + 10·1 = 20。

在第三个示例中,Limak 可以直接在每两个顶点之间跳转。有 3 对顶点 (s < t),所以答案是 3·1 = 3。