{"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 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_.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint one integer, denoting the sum of _f_(_s_, _t_) over all pairs of vertices (_s_, _t_) such that _s_ < _t_.\n\n[samples]\n\n## Note\n\nIn 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.","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_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]。\n\n## Input\n\n输入的第一行包含两个整数 #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] 条边连接的两个顶点。保证给定的边构成一棵树。\n\n## Output\n\n请输出一个整数，表示所有满足 #cf_span[s < t] 的顶点对 #cf_span[(s, t)] 的 #cf_span[f(s, t)] 之和。\n\n[samples]\n\n## Note\n\n在第一个样例中，给定的树有 #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]。","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 $.  \nLet $ k \\in \\mathbb{Z}^+ $ be the maximum jump distance.  \nDefine $ f(s, t) = \\left\\lceil \\frac{d(s, t)}{k} \\right\\rceil $ for $ s \\ne t $.\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_{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\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF771C","tags":["dfs and similar","dp","trees"],"sample_group":[["6 2\n1 2\n1 3\n2 4\n2 5\n4 6","20"],["13 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","114"],["3 5\n2 1\n3 1","3"]],"created_at":"2026-03-03 11:00:39"}}