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

The first line of the input contains two integers $ n $ and $ k $ ( $ 2\le n\le200000 $ , $ 1\le k\le5 $ ) — 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\le a_{i},b_{i}\le 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 $ .

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). :::align{center}  ::: There are $\dfrac{n(n-1)}2=15$ 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\times2+10\times1=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\times1=3 $ .