CF771C.Bear and Tree Jumps

A tree is an undirected connected graph without cycles. The distance between two vertices is the number of edges in a simple path between them.

Limak is a little polar bear. He lives in a tree that consists of n vertices, numbered 1 through n.

Limak recently learned how to jump. He can jump from a vertex to any vertex within distance at most k.

For a pair of vertices (s, t) we define f(s, t) as the minimum number of jumps Limak needs to get from s to t. Your task is to find the sum of f(s, t) over all pairs of vertices (s, t) such that s < t.

树是一类无向连通图，且不含环。两个顶点之间的距离定义为它们之间简单路径上的边数。

Limak 是一只小北极熊。他生活在一棵包含 $n$ 个顶点的树上，顶点编号为 $1$ 到 $n$。

最近，Limak 学会了跳跃。他可以从一个顶点跳到任意一个与其距离不超过 $k$ 的顶点。

对于一对顶点 $(s,\,t)$，我们定义 $f(s,\,t)$ 为 Limak 从 $s$ 到 $t$ 所需的最少跳跃次数。你的任务是计算所有满足 $s < t$ 的顶点对 $(s,\,t)$ 对应的 $f(s,\,t)$ 之和。

The first line of the input contains two integers n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ 5) — the number of vertices in the tree and the maximum allowed jump distance respectively.

The next n - 1 lines describe edges in the tree. The i-th of those lines contains two integers a__i and b__i (1 ≤ a__i, b__i ≤ n) — the indices on vertices connected with i-th edge.

It's guaranteed that the given edges form a tree.

输入的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 200\,000$，$1 \leq k \leq 5$）—— 分别表示树中顶点的数量和允许的最大跳跃距离。

接下来的 $n-1$ 行描述树中的边。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$）—— 表示第 $i$ 条边所连接的两个顶点的编号。

保证所给的边构成一棵树。

Print one integer, denoting the sum of f(s, t) over all pairs of vertices (s, t) such that s < t.

输出一个整数，表示对所有满足 $s < t$ 的顶点对 $(s, t)$ 的 $f(s, t)$ 之和。

In the first sample, the given tree has 6 vertices and it's displayed on the drawing below. Limak can jump to any vertex within distance at most 2. For example, from the vertex 5 he can jump to any of vertices: 1, 2 and 4 (well, he can also jump to the vertex 5 itself).

There are pairs of vertices (s, t) such that s < t. For 5 of those pairs Limak would need two jumps: (1, 6), (3, 4), (3, 5), (3, 6), (5, 6). For other 10 pairs one jump is enough. So, the answer is 5·2 + 10·1 = 20.

In the third sample, Limak can jump between every two vertices directly. There are 3 pairs of vertices (s < t), so the answer is 3·1 = 3.

在第一个样例中，给定的树有 6 个顶点，如下图所示。Limak 可以跳跃至距离不超过 2 的任意顶点。例如，从顶点 5 出发，他可以跳到顶点 1、2 和 4（当然，他也可以跳到顶点 5 自身）。

共有 对顶点 $ (s,,t) $ 满足 $ s < t $。其中，有 5 对顶点需要恰好两次跳跃才能到达：$ (1,,6),,(3,,4),,(3,,5),,(3,,6),,(5,,6) $；其余 10 对顶点只需一次跳跃即可。因此，答案为 $ 5 \cdot 2 + 10 \cdot 1 = 20 $。

在第三个样例中，Limak 可以直接在任意两个顶点之间跳跃。共有 3 对顶点满足 $ s < t $，因此答案为 $ 3 \cdot 1 = 3 $。