#P2351. [SDOI2012] 吊灯

[SDOI2012] 吊灯

题目背景

山东省省队选拔赛第二试(第一天)

题目描述

Alice 家里有一盏很大的吊灯。所谓吊灯,就是由很多个灯泡组成。只有一个灯泡是挂在天花板上的,剩下的灯泡都是挂在其他的灯泡上的。也就是说,整个吊灯实际上类似于一棵树。其中编号为 11 的灯泡是挂在天花板上的,剩下的灯泡都是挂在编号小于自己的灯泡上的。

现在,Alice 想要办一场派对,她想改造一下这盏吊灯,将灯泡换成不同的颜色。她希望相同颜色的灯泡都是相连的,并且每一种颜色的灯泡个数都是相同的。

Alice 希望你能告诉她,总共有哪些方案。

Alice 是一个贪心的孩子,如果她发现方案不够多,或者太多了,就会很不高兴,于是她会尝试调整。对于编号为 xxx1x\neq 1)的灯泡,如果原来是挂在编号为 fxf_x 的灯泡上,那么 Alice 会把第 xx 个灯泡挂到第 (fx+19940105)mod(x1)+1(f_x + 19940105)\bmod (x-1) + 1 个灯泡上。

由于九在古汉语中表示极大的数,于是,Alice 决定只调整 99 次。对于原始状态和每一次调整过的状态,Alice 希望你依次告诉她每种状态下有哪些方案。

输入格式

第一行一个整数 nn,表示灯泡的数量。

接下来一行,有 n1n-1 个整数 UiU_i,第 ii 个数表示第 i+1i+1 个灯泡挂在了第 UiU_i 个的下面。保证编号为 11 的灯泡是挂在天花板上的。数字之间用逗号(西文标点), 隔开且最后一个数字后面没有逗号。

输出格式

对于 1010 种状态下的方案,需要按照顺序依次输出。

对于每一种状态,需要先输出单独的一行,表示状态编号,如样例所示。

之后若干行,每行 11 个整数,表示划分方案中每种颜色的灯泡个数。

按升序输出。

6
1,2,3,4,5
Case #1:
1
2
3
6
Case #2:
1
2
6
Case #3:
1
3
6
Case #4:
1
3
6
Case #5:
1
3
6
Case #6:
1
2
6
Case #7:
1
2
3
6
Case #8:
1
6
Case #9:
1
2
6
Case #10:
1
3
6

提示

对于 20%20\% 的数据,n3×103n\leq 3\times 10^3

对于 40%40\% 的数据,n5×104n\leq 5\times 10^4

对于 50%50\% 的数据,n105n\leq 10^5

对于 60%60\% 的数据,n3×105n\leq 3\times 10^5

对于 70%70\% 的数据,n7×105n\leq 7\times 10^5

对于 100%100\% 的数据,1n1.2×1061\leq n\leq 1.2\times 10^6