Bear and Tree Jumps

题意翻译

有一棵 $n$ 个节点的树，树上住着一只熊。 若熊在节点 $u$，熊跳一次可以从 $u$ 跳到离 $u$ 树上距离 $\le k$ 的任意节点 $v$。 设 $f(s,t)$ 为熊从 $s$ 到 $t$ 跳的次数的最小值。 求 $\sum\limits_{1\le s<t\le n} f(s,t)$。 $2\le n\le 2\times 10^5,1\le k \le 5$

题目描述

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&lt;t $ .

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ k $ ( $ 2<=n<=200000 $ , $ 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.

输出格式

Print one integer, denoting the sum of $ f(s,t) $ over all pairs of vertices $ (s,t) $ such that $ s&lt;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

说明

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&lt;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&lt;t) $ , so the answer is $ 3·1=3 $ .

题意翻译

有一棵 $n$ 个节点的树，树上住着一只熊。 若熊在节点 $u$，熊跳一次可以从 $u$ 跳到离 $u$ 树上距离 $\le k$ 的任意节点 $v$。 设 $f(s,t)$ 为熊从 $s$ 到 $t$ 跳的次数的最小值。 求 $\sum\limits_{1\le s<t\le n} f(s,t)$。 $2\le n\le 2\times 10^5,1\le k \le 5$