H. Path Counting

Codeforces

IDCF954H

Time5000ms

Memory256MB

Difficulty—

combinatoricsdp

English · Original

Chinese · Translation

Formal · Original

You are given a rooted tree. Let's denote _d_(_x_) as depth of node _x_: depth of the root is 1, depth of any other node _x_ is _d_(_y_) + 1, where _y_ is a parent of _x_. The tree has the following property: every node _x_ with _d_(_x_) = _i_ has exactly _a__i_ children. Maximum possible depth of a node is _n_, and _a__n_ = 0. We define _f__k_ as the number of unordered pairs of vertices in the tree such that the number of edges on the simple path between them is equal to _k_. Calculate _f__k_ modulo 109 + 7 for every 1 ≤ _k_ ≤ 2_n_ - 2. ## Input The first line of input contains an integer _n_ (2 ≤ _n_ ≤ 5 000) — the maximum depth of a node. The second line of input contains _n_ - 1 integers _a_1, _a_2, ..., _a__n_ - 1 (2 ≤ _a__i_ ≤ 109), where _a__i_ is the number of children of every node _x_ such that _d_(_x_) = _i_. Since _a__n_ = 0, it is not given in the input. ## Output Print 2_n_ - 2 numbers. The _k_\-th of these numbers must be equal to _f__k_ modulo 109 + 7. [samples] ## Note This the tree from the first sample: <center>![image](https://espresso.codeforces.com/81cc5f2767d9eec33aa1efcb47ef6a4872480934.png)</center>

[{"iden":"statement","content":"你被给定一棵有根树。记 #cf_span[d(x)] 为节点 #cf_span[x] 的深度：根节点的深度为 #cf_span[1]，其他任意节点 #cf_span[x] 的深度为 #cf_span[d(y) + 1]，其中 #cf_span[y] 是 #cf_span[x] 的父节点。\n\n这棵树具有以下性质：每个满足 #cf_span[d(x) = i] 的节点 #cf_span[x] 恰好有 #cf_span[ai] 个子节点。节点的最大可能深度为 #cf_span[n]，且 #cf_span[an = 0]。\n\n我们定义 #cf_span[fk] 为树中满足简单路径上边数恰好为 #cf_span[k] 的无序顶点对的数量。\n\n请对每个 #cf_span[1 ≤ k ≤ 2n - 2]，计算 #cf_span[fk] 对 #cf_span[109 + 7] 取模的结果。\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 5 000]) —— 节点的最大深度。\n\n输入的第二行包含 #cf_span[n - 1] 个整数 #cf_span[a1, a2, ..., an - 1] (#cf_span[2 ≤ ai ≤ 109])，其中 #cf_span[ai] 表示每个满足 #cf_span[d(x) = i] 的节点 #cf_span[x] 的子节点数。由于 #cf_span[an = 0]，该值不在输入中给出。\n\n请输出 #cf_span[2n - 2] 个数。第 #cf_span[k] 个数必须等于 #cf_span[fk] 对 #cf_span[109 + 7] 取模的结果。"}},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 5 000]) —— 节点的最大深度。输入的第二行包含 #cf_span[n - 1] 个整数 #cf_span[a1, a2, ..., an - 1] (#cf_span[2 ≤ ai ≤ 109])，其中 #cf_span[ai] 表示每个满足 #cf_span[d(x) = i] 的节点 #cf_span[x] 的子节点数。由于 #cf_span[an = 0]，该值不在输入中给出。"},{"iden":"output","content":"请输出 #cf_span[2n - 2] 个数。第 #cf_span[k] 个数必须等于 #cf_span[fk] 对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入\n4\n2 2 2\n输出\n14 19 20 20 16 16\n\n输入\n3\n2 3\n输出\n8 13 6 9 "},{"iden":"note","content":"这是第一个样例中的树： "}]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 5000 $. Let $ a_i \in \mathbb{Z} $ for $ 1 \leq i \leq n-1 $, where $ a_i \geq 2 $, and $ a_n = 0 $. The tree is rooted at node of depth 1. For each node $ x $ at depth $ i $ ($ 1 \leq i < n $), it has exactly $ a_i $ children. Nodes at depth $ n $ are leaves (no children). Let $ d(x) $ denote the depth of node $ x $, with $ d(\text{root}) = 1 $. Let $ V $ be the set of all nodes in the tree. Let $ f_k $ be the number of unordered pairs $ \{u, v\} \subseteq V $, $ u \ne v $, such that the distance (number of edges) on the unique simple path between $ u $ and $ v $ is exactly $ k $. **Constraints** 1. $ 2 \leq n \leq 5000 $ 2. $ 2 \leq a_i \leq 10^9 $ for $ 1 \leq i \leq n-1 $ 3. $ a_n = 0 $ (implicit) 4. Compute $ f_k \mod (10^9 + 7) $ for all $ 1 \leq k \leq 2n - 2 $ **Objective** For each $ k \in \{1, 2, \dots, 2n-2\} $, compute: $$ f_k = \left| \left\{ \{u, v\} \subseteq V \,\middle|\, u \ne v,\, \text{dist}(u,v) = k \right\} \right| \mod (10^9 + 7) $$

Samples

Input #1

4
2 2 2

Output #1

14 19 20 20 16 16

Input #2

3
2 3

Output #2

8 13 6 9

API Response (JSON)

{
  "problem": {
    "name": "H. Path Counting",
    "description": {
      "content": "You are given a rooted tree. Let's denote _d_(_x_) as depth of node _x_: depth of the root is 1, depth of any other node _x_ is _d_(_y_) + 1, where _y_ is a parent of _x_. The tree has the following ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF954H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a rooted tree. Let's denote _d_(_x_) as depth of node _x_: depth of the root is 1, depth of any other node _x_ is _d_(_y_) + 1, where _y_ is a parent of _x_.\n\nThe tree has the following ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"你被给定一棵有根树。记 #cf_span[d(x)] 为节点 #cf_span[x] 的深度：根节点的深度为 #cf_span[1]，其他任意节点 #cf_span[x] 的深度为 #cf_span[d(y) + 1]，其中 #cf_span[y] 是 #cf_span[x] 的父节点。\\n\\n这棵树具有以下性质：每个满足 #cf_s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 5000 $.  \nLet $ a_i \\in \\mathbb{Z} $ for $ 1 \\leq i \\leq n-1 $, where $ a_i \\geq 2 $, and $ a_n = 0 $.  \nThe tree is rooted at node of d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments