树是没有环的无向连通图。两个顶点之间的距离是它们之间的简单路径中的边数。
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。