#include <bits/stdc++.h>
using ll = long long;
const int MAXN = 222222;
int N, K;
std::vector<int> adj[MAXN];
ll f[MAXN], g[MAXN];
std::vector<int> fv[MAXN];
int depth[MAXN];
template <typename T>
void rotr(std::vector<T>& v) {
  std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());
}
std::vector<int> dfs1(int cur, int par, int dep) {
  depth[cur] = dep;
  std::vector<int> ret(K);
  for (int nxt : adj[cur]) {
    if (nxt == par) continue;
    auto v = dfs1(nxt, cur, dep + 1);
    f[cur] += f[nxt] + v[0];
    ret[0] += v[K - 1];
    for (int i = 1; i < K; ++i) ret[i] += v[i - 1];
  }
  ++ret[0];
  fv[cur] = ret;
  return ret;
}
void dfs2(int cur, int par, std::vector<int> abv) {
  if (par != 0) {
    auto v = fv[cur];
    g[cur] = g[par] + f[par] - (f[cur] + v[0]) + abv[0] - 1;
    for (int nxt : adj[par]) {
      if (depth[nxt] < depth[cur]) continue;
      if (nxt == cur) continue;
      g[cur] += K == 1 ? fv[nxt][0] : fv[nxt][K - 1];
    }
    g[cur]++;
  }
  for (int nxt : adj[par]) {
    if (depth[nxt] < depth[cur]) continue;
    if (nxt == cur) continue;
    abv[0] += fv[nxt][K - 1];
    for (int i = 1; i < K; ++i) abv[i] += fv[nxt][i - 1];
  }
  rotr(abv);
  ++abv[0];
  for (int nxt : adj[cur]) {
    if (nxt == par) continue;
    dfs2(nxt, cur, abv);
  }
}
void dfs3(int cur, int par, std::vector<int> abv) {
  rotr(abv);
  for (int i = 0; i < K; ++i) abv[i] += fv[cur][i];
  for (int nxt : adj[cur]) {
    if (nxt == par) continue;
    auto tmp = abv;
    tmp[0] -= fv[nxt][K - 1];
    for (int i = 1; i < K; ++i) tmp[i] -= fv[nxt][i - 1];
    g[nxt] = g[cur] + f[cur] - (f[nxt] + fv[nxt][0]) + tmp[0];
    dfs3(nxt, cur, tmp);
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin >> N >> K;
  int u, v;
  for (int n = 1; n < N; ++n) {
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs1(1, 0, 0);
  fv[0] = fv[1];
  std::vector<int> hold(K);
  dfs3(1, 0, hold);
  ll tot = 0;
  for (int i = 1; i <= N; ++i) tot += f[i] + g[i];
  std::cout << tot / 2 << std::endl;
}

### Prompt

Create a solution in CPP for the following problem:

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

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

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

Examples

Input

6 2
1 2
1 3
2 4
2 5
4 6


Output

20


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


Output

114


Input

3 5
2 1
3 1


Output

3

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).

<image>

There are <image> 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.

### Response

```cpp
#include <bits/stdc++.h>
using ll = long long;
const int MAXN = 222222;
int N, K;
std::vector<int> adj[MAXN];
ll f[MAXN], g[MAXN];
std::vector<int> fv[MAXN];
int depth[MAXN];
template <typename T>
void rotr(std::vector<T>& v) {
  std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());
}
std::vector<int> dfs1(int cur, int par, int dep) {
  depth[cur] = dep;
  std::vector<int> ret(K);
  for (int nxt : adj[cur]) {
    if (nxt == par) continue;
    auto v = dfs1(nxt, cur, dep + 1);
    f[cur] += f[nxt] + v[0];
    ret[0] += v[K - 1];
    for (int i = 1; i < K; ++i) ret[i] += v[i - 1];
  }
  ++ret[0];
  fv[cur] = ret;
  return ret;
}
void dfs2(int cur, int par, std::vector<int> abv) {
  if (par != 0) {
    auto v = fv[cur];
    g[cur] = g[par] + f[par] - (f[cur] + v[0]) + abv[0] - 1;
    for (int nxt : adj[par]) {
      if (depth[nxt] < depth[cur]) continue;
      if (nxt == cur) continue;
      g[cur] += K == 1 ? fv[nxt][0] : fv[nxt][K - 1];
    }
    g[cur]++;
  }
  for (int nxt : adj[par]) {
    if (depth[nxt] < depth[cur]) continue;
    if (nxt == cur) continue;
    abv[0] += fv[nxt][K - 1];
    for (int i = 1; i < K; ++i) abv[i] += fv[nxt][i - 1];
  }
  rotr(abv);
  ++abv[0];
  for (int nxt : adj[cur]) {
    if (nxt == par) continue;
    dfs2(nxt, cur, abv);
  }
}
void dfs3(int cur, int par, std::vector<int> abv) {
  rotr(abv);
  for (int i = 0; i < K; ++i) abv[i] += fv[cur][i];
  for (int nxt : adj[cur]) {
    if (nxt == par) continue;
    auto tmp = abv;
    tmp[0] -= fv[nxt][K - 1];
    for (int i = 1; i < K; ++i) tmp[i] -= fv[nxt][i - 1];
    g[nxt] = g[cur] + f[cur] - (f[nxt] + fv[nxt][0]) + tmp[0];
    dfs3(nxt, cur, tmp);
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin >> N >> K;
  int u, v;
  for (int n = 1; n < N; ++n) {
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs1(1, 0, 0);
  fv[0] = fv[1];
  std::vector<int> hold(K);
  dfs3(1, 0, hold);
  ll tot = 0;
  for (int i = 1; i <= N; ++i) tot += f[i] + g[i];
  std::cout << tot / 2 << std::endl;
}

```