{"raw_statement":[{"iden":"statement","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 consists of _n_ vertices, numbered 1 through _n_.\n\nLimak recently learned how to jump. He can jump from a vertex to any vertex within distance at most _k_.\n\nFor 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_."},{"iden":"input","content":"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.\n\nThe 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.\n\nIt's guaranteed that the given edges form a tree."},{"iden":"output","content":"Print one integer, denoting the sum of _f_(_s_, _t_) over all pairs of vertices (_s_, _t_) such that _s_ < _t_."},{"iden":"examples","content":"Input\n\n6 2\n1 2\n1 3\n2 4\n2 5\n4 6\n\nOutput\n\n20\n\nInput\n\n13 3\n1 2\n3 2\n4 2\n5 2\n3 6\n10 6\n6 7\n6 13\n5 8\n5 9\n9 11\n11 12\n\nOutput\n\n114\n\nInput\n\n3 5\n2 1\n3 1\n\nOutput\n\n3"},{"iden":"note","content":"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).\n\n<center>![image](https://espresso.codeforces.com/2f64f096f9b26ecb178744d255b0b317185ae82b.png)</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.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"一棵树是无环的无向连通图。两个顶点之间的距离是它们之间简单路径上的边数。\n\nLimak 是一只小北极熊，他生活在一个包含 #cf_span[n] 个顶点的树中，顶点编号为 #cf_span[1] 到 #cf_span[n]。\n\nLimak 最近学会了跳跃。他可以从一个顶点跳到任意距离不超过 #cf_span[k] 的顶点。\n\n对于一对顶点 #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)] 之和。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[2 ≤ n ≤ 200 000], #cf_span[1 ≤ k ≤ 5])，分别表示树中的顶点数和最大允许跳跃距离。\n\n接下来的 #cf_span[n - 1] 行描述树中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n])，表示第 #cf_span[i] 条边连接的两个顶点。\n\n保证给定的边构成一棵树。\n\n请输出一个整数，表示所有满足 #cf_span[s < t] 的顶点对 #cf_span[(s, t)] 的 #cf_span[f(s, t)] 之和。\n\n在第一个样例中，给定的树有 #cf_span[6] 个顶点，如下面的图所示。Limak 可以跳到距离不超过 #cf_span[2] 的任意顶点。例如，从顶点 #cf_span[5] 出发，他可以跳到顶点 #cf_span[1]、#cf_span[2] 和 #cf_span[4]（当然，他也可以跳到顶点 #cf_span[5] 自身）。\n\n共有 #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]。\n\n在第三个样例中，Limak 可以直接在任意两个顶点之间跳跃。共有 #cf_span[3] 对顶点 #cf_span[(s < t)]，因此答案为 #cf_span[3·1 = 3]。"},{"iden":"input","content":"输入的第一行包含两个整数 #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] 条边连接的两个顶点。保证给定的边构成一棵树。"},{"iden":"output","content":"请输出一个整数，表示所有满足 #cf_span[s < t] 的顶点对 #cf_span[(s, t)] 的 #cf_span[f(s, t)] 之和。"},{"iden":"examples","content":"输入：\n6 2\n1 2\n1 3\n2 4\n2 5\n4 6\n输出：\n20\n\n输入：\n13 3\n1 2\n3 2\n4 2\n5 2\n3 6\n10 6\n6 7\n6 13\n5 8\n5 9\n9 11\n11 12\n输出：\n114\n\n输入：\n3 5\n2 1\n3 1\n输出：\n3"},{"iden":"note","content":"在第一个样例中，给定的树有 #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]。\n\n在第三个样例中，Limak 可以直接在任意两个顶点之间跳跃。共有 #cf_span[3] 对顶点 #cf_span[(s < t)]，因此答案为 #cf_span[3·1 = 3]。"}],"sample_group":[],"show_order":[],"formal_statement":"**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, v \\in V $.  \nLet $ k \\in \\mathbb{Z}^+ $ be the maximum jump distance.  \n\nFor any pair $ (s, t) \\in V \\times V $ with $ s \\ne t $, define $ f(s, t) $ as the minimum number of jumps required to travel from $ s $ to $ t $, where each jump covers distance at most $ k $.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 200{,}000 $  \n2. $ 1 \\le k \\le 5 $  \n3. The graph is a tree.  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{\\substack{s, t \\in V \\\\ s < t}} f(s, t)\n$$  \nwhere $ f(s, t) = \\left\\lceil \\frac{d(s, t)}{k} \\right\\rceil $.","simple_statement":null,"has_page_source":false}