|
||||||||||
Rikka 与子集 IVTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 179 Accepted Submission(s): 42 Problem Description 我们都知道,Rikka 的数学不好,Yuta 很担心这个状况。所以他给了 Rikka 一些数学题来练习,下面是其中一道。 给定一棵 $n$ 个点的有标号树,问树上有多少大小为 $i$ 的连通块,对于 $1\le i\le n$ 输出答案。 两个连通块不同,当且仅当两个连通块的点集不同。 Input 第一行一个正整数 $T$($1\le T\le 100$),表示测试数据组数。 对于每组数据,第一行一个整数 $n$($2\le n\le 10^5$),表示树上点的个数。 第二行 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$($1\le p_i < i$),$p_i$ 表示 $i$ 与 $p_i$ 之间有一条边相连。 保证数据满足 $\sum n\le 4\times 10^5$。 Output 对于每组数据,输出一行 $n$ 个整数,第 $i$ 个整数表示大小为 $i$ 的连通块个数,对 $998244353$ 取模。 Sample Input
Sample Output
Hint 本题中你可能需要更大的栈,我们建议在主函数使用如下代码扩充栈空间。 int main() { int size = 512 << 20; // 512M \_\_asm\_\_("movq %0, %%rsp\n" :: "r"((char *)malloc(size) + size)); // Your code exit(0); } 请注意,你必须使用 $\texttt{exit}$ 函数结束程序,否则你的程序将被判为 RE。 Source | ||||||||||
|