P2351 [SDOI2012] Chandelier

Shandong Provincial Team Selection, Second Test (Day 1).

Alice 家里有一盏很大的吊灯。所谓吊灯，就是由很多个灯泡组成。只有一个灯泡是挂在天花板上的，剩下的灯泡都是挂在其他的灯泡上的。也就是说，整个吊灯实际上类似于**一棵树**。其中编号为 $1$ 的灯泡是挂在天花板上的，剩下的灯泡都是挂在编号小于自己的灯泡上的。 现在，Alice 想要办一场派对，她想改造一下这盏吊灯，将灯泡换成不同的颜色。她希望相同颜色的灯泡都是相连的，并且每一种颜色的灯泡个数都是相同的。 Alice 希望你能告诉她，总共有哪些方案。 Alice 是一个贪心的孩子，如果她发现方案不够多，或者太多了，就会很不高兴，于是她会尝试调整。对于编号为 $x$（$x\neq 1$）的灯泡，如果原来是挂在编号为 $f_x$ 的灯泡上，那么 Alice 会把第 $x$ 个灯泡挂到第 $(f_x + 19940105)\bmod (x-1) + 1$ 个灯泡上。 由于九在古汉语中表示极大的数，于是，Alice 决定只调整 $9$ 次。对于原始状态和每一次调整过的状态，Alice 希望你依次告诉她每种状态下有哪些方案。

第一行一个整数 $n$，表示灯泡的数量。 接下来一行，有 $n-1$ 个整数 $U_i$，第 $i$ 个数表示第 $i+1$ 个灯泡挂在了第 $U_i$ 个的下面。保证编号为 $1$ 的灯泡是挂在天花板上的。数字之间用逗号（西文标点）`,` 隔开且最后一个数字后面没有逗号。

For the plans of the $10$ states, output them in order. For each state, first output a separate line indicating the state index, as shown in the sample. Then output several lines, each containing $1$ integer, representing the number of bulbs per color in a valid partition. Output in ascending order.

For $20\%$ of the testdata, $n \leq 3 \times 10^3$. For $40\%$ of the testdata, $n \leq 5 \times 10^4$. For $50\%$ of the testdata, $n \leq 10^5$. For $60\%$ of the testdata, $n \leq 3 \times 10^5$. For $70\%$ of the testdata, $n \leq 7 \times 10^5$. For $100\%$ of the testdata, $1 \leq n \leq 1.2 \times 10^6$. Translated by ChatGPT 5