F. Heaps

Codeforces

IDCF955F

Time2000ms

Memory512MB

Difficulty—

dptrees

English · Original

Chinese · Translation

Formal · Original

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. * 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. Denote _dp__k_(_u_) as maximum depth of _k_\-ary heap in the subtree of _u_ (including _u_). Your goal is to compute . ## Input The first line contains an integer _n_ denoting the size of the tree (2 ≤ _n_ ≤ 3·105). The next _n_ - 1 lines contain two integers _u_, _v_ each, describing vertices connected by _i_\-th edge. It's guaranteed that the given configuration forms a tree. ## Output Output the answer to the task. [samples] ## Note Consider sample case one. For _k_ ≥ 3 all _dp__k_ will be equal to 1. For _k_ = 2 _dp__k_ is 2 if and 1 otherwise. For _k_ = 1 _dp__k_ values are (3, 1, 2, 1) respectively. To sum up, 4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21.

给你一棵有 #cf_span[n] 个顶点、根为 #cf_span[1] 的树。我们说在 #cf_span[u] 处存在一个深度为 #cf_span[m] 的 #cf_span[k]-叉堆，当且仅当满足以下条件：记 #cf_span[dpk(u)] 为以 #cf_span[u] 为根的子树中（包含 #cf_span[u]）最大的 #cf_span[k]-叉堆的深度。你的目标是计算。第一行包含一个整数 #cf_span[n]，表示树的大小 #cf_span[(2 ≤ n ≤ 3·105)]。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u], #cf_span[v]，描述第 #cf_span[i] 条边连接的两个顶点。保证给定的结构构成一棵树。请输出该问题的答案。考虑第一个样例。对于 #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]。 ## Input 第一行包含一个整数 #cf_span[n]，表示树的大小 #cf_span[(2 ≤ n ≤ 3·105)]。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u], #cf_span[v]，描述第 #cf_span[i] 条边连接的两个顶点。保证给定的结构构成一棵树。 ## Output 请输出该问题的答案。 [samples] ## Note 考虑第一个样例。对于 #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]。

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: - $ u $ has at most $ k $ children, - Each child $ v $ of $ u $ is the root of a $ k $-ary heap of depth $ d-1 $, - The heap property is satisfied (i.e., the structure is a complete $ k $-ary tree of depth $ d $). Define $ f(k) = \sum_{u=1}^{n} \text{dp}_k(u) $. Compute $ \sum_{k=1}^{n} f(k) $. Note: 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 $.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "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*...",
      "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第...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments