F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Rikka 与子集 IV

Time 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
3 5 1 1 2 2 6 1 1 2 2 3 6 1 1 2 2 5
 

Sample Output
5 4 4 3 1 6 5 5 4 3 1 6 5 5 5 3 1
 

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
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-10 12:25:08, Gzip enabled