English · Original
Chinese · Translation
Formal · Original
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 _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.
## Output
Print one integer, denoting the sum of _f_(_s_, _t_) over all pairs of vertices (_s_, _t_) such that _s_ < _t_.
[samples]
## 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).
<center></center>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.
一棵树是无环的无向连通图。两个顶点之间的距离是它们之间简单路径上的边数。
Limak 是一只小北极熊，他生活在一个包含 #cf_span[n] 个顶点的树中，顶点编号为 #cf_span[1] 到 #cf_span[n]。
Limak 最近学会了跳跃。他可以从一个顶点跳到距离至多为 #cf_span[k] 的任意顶点。
对于一对顶点 #cf_span[(s, t)]，我们定义 #cf_span[f(s, t)] 为 Limak 从 #cf_span[s] 到达 #cf_span[t] 所需的最少跳跃次数。你的任务是求出所有满足 #cf_span[s < t] 的顶点对 #cf_span[(s, t)] 的 #cf_span[f(s, t)] 之和。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200 000]，#cf_span[1 ≤ k ≤ 5]），分别表示树中的顶点数和最大允许跳跃距离。
接下来的 #cf_span[n - 1] 行描述了树中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]），表示第 #cf_span[i] 条边连接的两个顶点。
保证给定的边构成一棵树。
请输出一个整数，表示所有满足 #cf_span[s < t] 的顶点对 #cf_span[(s, t)] 的 #cf_span[f(s, t)] 之和。
在第一个样例中，给定的树有 #cf_span[6] 个顶点，如下图所示。Limak 可以跳到距离至多为 #cf_span[2] 的任意顶点。例如，从顶点 #cf_span[5] 出发，他可以跳到顶点 #cf_span[1]、#cf_span[2] 和 #cf_span[4]（当然，他也可以跳到顶点 #cf_span[5] 自身）。
共有 #cf_span[\binom{6}{2} = 15] 对顶点 #cf_span[(s, t)] 满足 #cf_span[s < t]。其中 #cf_span[5] 对需要两次跳跃：#cf_span[(1, 6), (3, 4), (3, 5), (3, 6), (5, 6)]；其余 #cf_span[10] 对只需一次跳跃。因此答案为 #cf_span[5·2 + 10·1 = 20]。
在第三个样例中，Limak 可以直接在任意两个顶点之间跳跃。共有 #cf_span[3] 对顶点 #cf_span[(s < t)]，因此答案为 #cf_span[3·1 = 3]。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200 000]，#cf_span[1 ≤ k ≤ 5]），分别表示树中的顶点数和最大允许跳跃距离。接下来的 #cf_span[n - 1] 行描述了树中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]），表示第 #cf_span[i] 条边连接的两个顶点。保证给定的边构成一棵树。
## Output
请输出一个整数，表示所有满足 #cf_span[s < t] 的顶点对 #cf_span[(s, t)] 的 #cf_span[f(s, t)] 之和。
[samples]
## Note
在第一个样例中，给定的树有 #cf_span[6] 个顶点，如下图所示。Limak 可以跳到距离至多为 #cf_span[2] 的任意顶点。例如，从顶点 #cf_span[5] 出发，他可以跳到顶点 #cf_span[1]、#cf_span[2] 和 #cf_span[4]（当然，他也可以跳到顶点 #cf_span[5] 自身）。共有 #cf_span[\binom{6}{2} = 15] 对顶点 #cf_span[(s, t)] 满足 #cf_span[s < t]。其中 #cf_span[5] 对需要两次跳跃：#cf_span[(1, 6), (3, 4), (3, 5), (3, 6), (5, 6)]；其余 #cf_span[10] 对只需一次跳跃。因此答案为 #cf_span[5·2 + 10·1 = 20]。
在第三个样例中，Limak 可以直接在任意两个顶点之间跳跃。共有 #cf_span[3] 对顶点 #cf_span[(s < t)]，因此答案为 #cf_span[3·1 = 3]。
**Definitions**
Let $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $.
Let $ d(u, v) $ denote the distance (number of edges in the unique simple path) between vertices $ u $ and $ v $.
Let $ k \in \mathbb{Z}^+ $ be the maximum jump distance.
Define $ f(s, t) = \left\lceil \frac{d(s, t)}{k} \right\rceil $ for $ s \ne t $.
**Constraints**
1. $ 2 \le n \le 200{,}000 $
2. $ 1 \le k \le 5 $
3. The graph is a tree.
**Objective**
Compute:
$$
\sum_{1 \le s < t \le n} f(s, t) = \sum_{1 \le s < t \le n} \left\lceil \frac{d(s, t)}{k} \right\rceil
$$
API Response (JSON)
{
"problem": {
"name": "C. Bear and Tree Jumps",
"description": {
"content": "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 c",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF771C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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.\n\nLimak is a little polar bear. He lives in a tree that c...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "一棵树是无环的无向连通图。两个顶点之间的距离是它们之间简单路径上的边数。\n\nLimak 是一只小北极熊，他生活在一个包含 #cf_span[n] 个顶点的树中，顶点编号为 #cf_span[1] 到 #cf_span[n]。\n\nLimak 最近学会了跳跃。他可以从一个顶点跳到距离至多为 #cf_span[k] 的任意顶点。\n\n对于一对顶点 #cf_span[(s, t)]，我们定义 #cf_spa...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $. \nLet $ d(u, v) $ denote the distance (number of edges in the unique simple path) between vertices $ u $ and $ v $. \nLe...",
"is_translate": false,
"language": "Formal"
}
]
}