Bear and Tree Jumps
Contest: VK Cup 2017 - Round 1
Difficulty rating: 2100
Tags: dfs and similar, dp, trees

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.

Input format:
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 ai and bi (1 ≤ ai, bi ≤ n) — the indices on vertices connected with i-th edge.

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

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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 $$\frac{n(n-1)}{2} = 15$$ 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.

Example input:
6 2
1 2
1 3
2 4
2 5
4 6

Example output:
20

Example input:
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

Example output:
114

Editorial:
It's a known problem to count the sum of distances for all pairs of vertices. For each edge, we should add to the answer the number of times this edge appears in a path between some two vertices. If sv denotes the size of the subtree of the vertex v (we can first root the tree in 1), we should add sv·(n - sv) to the sum.
In this problem, the answer is around $$\frac{s}{k}$$, where S is the answer for the known problem described above. But for each path with length L, we should add $$\left\lceil \frac{L}{k} \right\rceil = \frac{L + f(L,k)}{k}$$ to the answer, where f(L, k) says how much we must add to L to get a number divisible by k (f(10, 3) = 2, f(11, 3) = 1, f(12, 3) = 0). We know the sum of $$\frac{L}{K}$$ because it's $$\frac{s}{k}$$ in total. What remains is to compute the sum of f(L, k). To achieve that, for each remainder modulo k, we want to know the number of paths with length that has this remainder. For example, if k = 3 and there are 200 paths with remainder 1, they all have f(L, k) = 2, so we should add 200·2 to the answer.
Let's root the tree in any vertex and do bottom-up dp. For each subtree we compute the k values: for each remainder modulo k how many paths (starting from the root of this subtree) have this remainder. We can merge two subtrees in O(k2), so the total complexity is O(n·k2). See my code for details.