D. Stranger Trees

Codeforces

IDCF917D

Time1000ms

Memory256MB

Difficulty—

dpmathmatricestrees

English · Original

Chinese · Translation

Formal · Original

Will shares a psychic connection with the Upside Down Monster, so everything the monster knows, Will knows. Suddenly, he started drawing, page after page, non-stop. Joyce, his mom, and Chief Hopper put the drawings together, and they realized, it's a labeled tree! <center>![image](https://espresso.codeforces.com/9584d2f12c27d335f9648838aa77d3fa8ede307d.png)</center>A tree is a connected acyclic graph. Will's tree has _n_ vertices. Joyce and Hopper don't know what that means, so they're investigating this tree and similar trees. For each _k_ such that 0 ≤ _k_ ≤ _n_ - 1, they're going to investigate all labeled trees with _n_ vertices that share exactly _k_ edges with Will's tree. Two labeled trees are different if and only if there's a pair of vertices (_v_, _u_) such that there's an edge between _v_ and _u_ in one tree and not in the other one. Hopper and Joyce want to know how much work they have to do, so they asked you to tell them the number of labeled trees with _n_ vertices that share exactly _k_ edges with Will's tree, for each _k_. The answer could be very large, so they only asked you to tell them the answers modulo 1000000007 = 109 + 7. ## Input The first line of input contains a single integer _n_ (2 ≤ _n_ ≤ 100) — the size of the tree. The next _n_ - 1 lines contain the edges of Will's tree. Each line contains two integers _v_ and _u_ (1 ≤ _v_, _u_ ≤ _n_, _v_ ≠ _u_), endpoints of an edge. It is guaranteed that the given graph is a tree. ## Output Print _n_ integers in one line. _i_\-th integer should be the number of the number of labeled trees with _n_ vertices that share exactly _i_ - 1 edges with Will's tree, modulo 1000 000 007 = 109 + 7. [samples]

Will 与颠倒世界的怪物拥有心灵感应，因此怪物知道的一切，Will 也知道。突然间，他开始不停歇地一页接一页地绘画。他的母亲 Joyce 和警长 Hopper 将这些画拼合起来，发现那是一棵带标号的树！树是一个连通的无环图。Will 的树有 #cf_span[n] 个顶点。Joyce 和 Hopper 不知道这意味着什么，因此他们正在研究这棵树以及类似的树。对于每个 #cf_span[0 ≤ k ≤ n - 1]，他们将研究所有具有 #cf_span[n] 个顶点的带标号树，这些树与 Will 的树恰好共享 #cf_span[k] 条边。两棵带标号的树不同，当且仅当存在一对顶点 #cf_span[(v, u)]，使得其中一棵树中有边连接 #cf_span[v] 和 #cf_span[u]，而另一棵树中没有。 Hopper 和 Joyce 想知道他们需要做多少工作，因此他们请你告诉他们，对于每个 #cf_span[k]，有多少棵具有 #cf_span[n] 个顶点的带标号树恰好与 Will 的树共享 #cf_span[k] 条边。答案可能非常大，因此他们只要求你输出答案对 #cf_span[1000000007 = 109 + 7] 取模的结果。输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 100]) —— 树的大小。接下来的 #cf_span[n - 1] 行包含 Will 的树的边。每行包含两个整数 #cf_span[v] 和 #cf_span[u] (#cf_span[1 ≤ v, u ≤ n], #cf_span[v ≠ u])，表示一条边的两个端点。保证给定的图是一棵树。请在一行中输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数应为具有 #cf_span[n] 个顶点的带标号树中，恰好与 Will 的树共享 #cf_span[i - 1] 条边的树的数量，对 #cf_span[1000 000 007 = 109 + 7] 取模。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 100]) —— 树的大小。接下来的 #cf_span[n - 1] 行包含 Will 的树的边。每行包含两个整数 #cf_span[v] 和 #cf_span[u] (#cf_span[1 ≤ v, u ≤ n], #cf_span[v ≠ u])，表示一条边的两个端点。保证给定的图是一棵树。 ## Output 请在一行中输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数应为具有 #cf_span[n] 个顶点的带标号树中，恰好与 Will 的树共享 #cf_span[i - 1] 条边的树的数量，对 #cf_span[1000 000 007 = 109 + 7] 取模。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 100 $, be the number of vertices. Let $ T^* = (V, E^*) $ be Will's labeled tree, where $ V = \{1, 2, \dots, n\} $ and $ |E^*| = n-1 $. Let $ \mathcal{T}_n $ be the set of all labeled trees on $ n $ vertices. **Constraints** - $ |E^*| = n - 1 $ - For any $ T = (V, E) \in \mathcal{T}_n $, $ |E| = n - 1 $ **Objective** For each $ k \in \{0, 1, \dots, n-1\} $, compute: $$ a_k = \left| \left\{ T \in \mathcal{T}_n \mid |E \cap E^*| = k \right\} \right| \mod 1000000007 $$ Output $ a_0, a_1, \dots, a_{n-1} $.

Samples

Input #1

3
1 2
1 3

Output #1

0 2 1

Input #2

Output #2

1 7 7 1

Input #3

Output #3

0 9 6 1

API Response (JSON)

{
  "problem": {
    "name": "D. Stranger Trees",
    "description": {
      "content": "Will shares a psychic connection with the Upside Down Monster, so everything the monster knows, Will knows. Suddenly, he started drawing, page after page, non-stop. Joyce, his mom, and Chief Hopper pu",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF917D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Will shares a psychic connection with the Upside Down Monster, so everything the monster knows, Will knows. Suddenly, he started drawing, page after page, non-stop. Joyce, his mom, and Chief Hopper pu...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Will 与颠倒世界的怪物拥有心灵感应，因此怪物知道的一切，Will 也知道。突然间，他开始不停歇地一页接一页地绘画。他的母亲 Joyce 和警长 Hopper 将这些画拼合起来，发现那是一棵带标号的树！\n\n树是一个连通的无环图。Will 的树有 #cf_span[n] 个顶点。Joyce 和 Hopper 不知道这意味着什么，因此他们正在研究这棵树以及类似的树。对于每个 #cf_span[0 ≤...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 100 $, be the number of vertices.  \nLet $ T^* = (V, E^*) $ be Will's labeled tree, where $ V = \\{1, 2, \\dots, n\\} $ and $ |E^*| = n-1 $.  \nL...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments