102875: [AtCoder]ABC287 F - Components

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $500$ points

Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$-th edge connects vertex $a_i$ and vertex $b_i$.

Solve the following problem for each $x=1,2,\ldots,N$:

  • There are $(2^N-1)$ non-empty subsets $V$ of the tree's vertices. Find the number, modulo $998244353$, of such $V$ that the subgraph induced by $V$ has exactly $x$ connected components.
What is an induced subgraph? Let $S$ be the subset of the vertices of a graph $G$; then the subgraph of $G$ induced by $S$ is a graph whose vertex set is $S$ and whose edge set consists of all edges of $G$ whose both ends are contained in $S$.

Constraints

  • $1 \leq N \leq 5000$
  • $1 \leq a_i \lt b_i \leq N$
  • The given graph is a tree.

Input

The input is given from Standard Input in the following format:

$N$
$a_1$ $b_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$

Output

Print $N$ lines.
The $i$-th line should contain the answer for $x=i$.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

10
5
0
0

The induced subgraph will have two connected components in the following five cases and one in the others.

  • $V = \{1,2,4\}$
  • $V = \{1,3\}$
  • $V = \{1,3,4\}$
  • $V = \{1,4\}$
  • $V = \{2,4\}$

Sample Input 2

2
1 2

Sample Output 2

3
0

Sample Input 3

10
3 4
3 6
6 9
1 3
2 4
5 6
6 10
1 8
5 7

Sample Output 3

140
281
352
195
52
3
0
0
0
0

Input

题意翻译

有一棵大小为 $n$ 的树，节点编号 $1\dots n$，从中任意选出一些点，显然有 $2^n-1$ 种方案。每一种选法中选择的点都会形成一些连通块，对于 $x=1\dots n$，求连通块数量恰好是 $x$ 的选法数量，对 $998244353$ 取模。

Output

分数：500分

问题描述

给你一棵有N个顶点的树。顶点编号为1到N，第i条边连接顶点a_i和顶点b_i。

对每个x=1,2,...,N，解决以下问题：

  • 树的顶点有$(2^N-1)$个非空子集V。求满足子图由V诱导且恰好有x个连通分量的V的数量，对998244353取模。
什么是诱导子图？ 设S是图G的顶点子集；则G由S诱导的子图是一个图，其顶点集为S，其边集由G中两端点均在S中的所有边组成。

限制条件

  • $1 \leq N \leq 5000$
  • $1 \leq a_i \lt b_i \leq N$
  • 给定的图是一棵树。

输入

输入从标准输入按以下格式给出：

$N$
$a_1$ $b_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$

输出

打印N行。
第i行应包含x=i时的答案。

样例输入1

4
1 2
2 3
3 4

样例输出1

10
5
0
0

在以下五种情况下，诱导子图将有两个连通分量，其他情况有一个连通分量。

  • $V = \{1,2,4\}$
  • $V = \{1,3\}$
  • $V = \{1,3,4\}$
  • $V = \{1,4\}$
  • $V = \{2,4\}$

样例输入2

2
1 2

样例输出2

3
0

样例输入3

10
3 4
3 6
6 9
1 3
2 4
5 6
6 10
1 8
5 7

样例输出3

140
281
352
195
52
3
0
0
0
0

Source/Category

加入题单

上一题 下一题 算法标签：