102697: [AtCoder]ABC269 Ex - Antichain
Description
Score : $600$ points
Problem Statement
We have a rooted tree $T$ with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i$ $(2 \leq i \leq N)$ is vertex $P_i$.
A non-empty subset $S$ of the vertex set $V = \lbrace 1, 2,\dots, N\rbrace$ of $T$ is said to be a good vertex set when it satisfies the following condition.
- For every pair of different vertices $(u, v)$ in $S$, the following holds: $u$ is not an ancestor of $v$.
For each $K = 1, 2, \dots, N$, find the number, modulo $998244353$, of good vertex sets with exactly $K$ vertices.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq P_i \lt i$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $P_2$ $P_3$ $\dots$ $P_N$
Output
Print $N$ lines. The $i$-th line should contain the answer for $K = i$.
Sample Input 1
4 1 2 1
Sample Output 1
4 2 0 0
For each $1 \leq K \leq N$, the good vertex sets of size $K$ are listed below.
- $K=1$: $\lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace$.
- $K=2$: $\lbrace 2, 4 \rbrace, \lbrace 3, 4 \rbrace$.
- $K=3,4$: There is none.
Sample Input 2
6 1 1 2 2 5
Sample Output 2
6 6 2 0 0 0
Sample Input 3
6 1 1 1 1 1
Sample Output 3
6 10 10 5 1 0
Sample Input 4
10 1 2 1 2 1 1 2 6 9
Sample Output 4
10 30 47 38 16 3 0 0 0 0
Input
题意翻译
现有节点编号分别为 $1\sim N$ 的树 $T$，其中 $1$ 为根，$i(2\le i\le N)$ 的父亲节点为 $P_i$。 把一个 $T$ 点集 $V=\{1,2,\cdots,N\}$ 的子集 $S$ 称为好的，当且仅当满足以下条件： - 任意一个 $S$ 中的二元组 $(u,v)$ 都满足 $u$ 不是 $v$ 的祖先。 请你对于每一个 $K=1,2,\cdots,N$ 求出，大小为 $K$ 的好子集个数 $\mod 998244353$ 的值。Output
得分：$600$分
问题描述
我们有一个有根树$T$，有$N$个顶点，编号为$1$到$N$。顶点$1$是根，顶点$i$ $(2 \leq i \leq N)$的父顶点是顶点$P_i$。
顶点集$V = \lbrace 1, 2,\dots, N\rbrace$中的非空子集$S$被认为是 好的顶点集 ，当它满足以下条件时。
- 对于$S$中的每一对不同的顶点$(u, v)$，满足以下条件：$u$不是$v$的祖先。
对于每个$K = 1, 2, \dots, N$，找出有正好$K$个顶点的良好顶点集的数量，对$998244353$取模。
约束
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq P_i \lt i$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出以下格式：
$N$ $P_2$ $P_3$ $\dots$ $P_N$
输出
打印$N$行。第$i$行应包含对于$K = i$的答案。
样例输入1
4 1 2 1
样例输出1
4 2 0 0
对于每个$1 \leq K \leq N$，大小为$K$的良好顶点集如下所示。
- $K=1$: $\lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace$。
- $K=2$: $\lbrace 2, 4 \rbrace, \lbrace 3, 4 \rbrace$。
- $K=3,4$: 不存在。
样例输入2
6 1 1 2 2 5
样例输出2
6 6 2 0 0 0
样例输入3
6 1 1 1 1 1
样例输出3
6 10 10 5 1 0
样例输入4
10 1 2 1 2 1 1 2 6 9
样例输出4
10 30 47 38 16 3 0 0 0 0