{"problem":{"name":"F. Heaps","description":{"content":"You're given a tree with _n_ vertices rooted at 1. We say that there's a _k_\\-ary heap of depth _m_ located at _u_ if the following holds: *   For _m_ = 1 _u_ itself is a _k_\\-ary heap of depth 1. *","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF955F"},"statements":[{"statement_type":"Markdown","content":"You're given a tree with _n_ vertices rooted at 1.\n\nWe say that there's a _k_\\-ary heap of depth _m_ located at _u_ if the following holds:\n\n*   For _m_ = 1 _u_ itself is a _k_\\-ary heap of depth 1.\n*   For _m_ > 1 vertex _u_ is a _k_\\-ary heap of depth _m_ if **at least** _k_ of its children are _k_\\-ary heaps of depth **at least** _m_ - 1.\n\nDenote _dp__k_(_u_) as maximum depth of _k_\\-ary heap in the subtree of _u_ (including _u_). Your goal is to compute .\n\n## Input\n\nThe first line contains an integer _n_ denoting the size of the tree (2 ≤ _n_ ≤ 3·105).\n\nThe next _n_ - 1 lines contain two integers _u_, _v_ each, describing vertices connected by _i_\\-th edge.\n\nIt's guaranteed that the given configuration forms a tree.\n\n## Output\n\nOutput the answer to the task.\n\n[samples]\n\n## Note\n\nConsider sample case one.\n\nFor _k_ ≥ 3 all _dp__k_ will be equal to 1.\n\nFor _k_ = 2 _dp__k_ is 2 if and 1 otherwise.\n\nFor _k_ = 1 _dp__k_ values are (3, 1, 2, 1) respectively.\n\nTo sum up, 4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给你一棵有 #cf_span[n] 个顶点、根为 #cf_span[1] 的树。\n\n我们说在 #cf_span[u] 处存在一个深度为 #cf_span[m] 的 #cf_span[k]-叉堆，当且仅当满足以下条件：\n\n记 #cf_span[dpk(u)] 为以 #cf_span[u] 为根的子树中（包含 #cf_span[u]）最大的 #cf_span[k]-叉堆的深度。你的目标是计算 。\n\n第一行包含一个整数 #cf_span[n]，表示树的大小 #cf_span[(2 ≤ n ≤ 3·105)]。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u], #cf_span[v]，描述第 #cf_span[i] 条边连接的两个顶点。\n\n保证给定的结构构成一棵树。\n\n请输出该问题的答案。\n\n考虑第一个样例。\n\n对于 #cf_span[k ≥ 3]，所有 #cf_span[dpk] 都等于 #cf_span[1]。\n\n对于 #cf_span[k = 2]，如果  则 #cf_span[dpk] 为 #cf_span[2]，否则为 #cf_span[1]。\n\n对于 #cf_span[k = 1]，#cf_span[dpk] 的值分别为 #cf_span[(3, 1, 2, 1)]。\n\n综上，#cf_span[4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21]。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]，表示树的大小 #cf_span[(2 ≤ n ≤ 3·105)]。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u], #cf_span[v]，描述第 #cf_span[i] 条边连接的两个顶点。保证给定的结构构成一棵树。\n\n## Output\n\n请输出该问题的答案。\n\n[samples]\n\n## Note\n\n考虑第一个样例。对于 #cf_span[k ≥ 3]，所有 #cf_span[dpk] 都等于 #cf_span[1]。对于 #cf_span[k = 2]，如果  则 #cf_span[dpk] 为 #cf_span[2]，否则为 #cf_span[1]。对于 #cf_span[k = 1]，#cf_span[dpk] 的值分别为 #cf_span[(3, 1, 2, 1)]。综上，#cf_span[4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ T $ be a rooted tree with $ n $ vertices, rooted at vertex $ 1 $. For each vertex $ u $ and integer $ k \\geq 1 $, define $ \\text{dp}_k(u) $ as the maximum depth of a $ k $-ary heap rooted at $ u $ within the subtree of $ u $, where a $ k $-ary heap of depth $ d $ rooted at $ u $ requires that:\n\n- $ u $ has at most $ k $ children,\n- Each child $ v $ of $ u $ is the root of a $ k $-ary heap of depth $ d-1 $,\n- The heap property is satisfied (i.e., the structure is a complete $ k $-ary tree of depth $ d $).\n\nDefine $ f(k) = \\sum_{u=1}^{n} \\text{dp}_k(u) $.\n\nCompute $ \\sum_{k=1}^{n} f(k) $.\n\nNote: For each $ k $, $ \\text{dp}_k(u) $ is the largest integer $ d $ such that the subtree rooted at $ u $ contains a complete $ k $-ary tree of depth $ d $ with root $ u $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF955F","tags":["dp","trees"],"sample_group":[["4\n1 3\n2 3\n4 3","21"],["4\n1 2\n2 3\n3 4","22"]],"created_at":"2026-03-03 11:00:39"}}