新学会一种很骚的求子树大小的方法，很简单。这道题假如用dfs会T。
题干:
题目描述Alice家里有一盏很大的吊灯。所谓吊灯，就是由很多个灯泡组成。只有一个灯泡是挂在天花板上的，剩下的灯泡都是挂在其他的灯泡上的。也就是说，整个吊灯实际上类似于[b]一棵树[/b]。其中编号为 1 的灯泡是挂在天花板上的，剩下的灯泡都是挂在编号小于自己的灯泡上的。现在，Alice想要办一场派对，她想改造一下这盏吊灯，将灯泡换成不同的颜色。她希望相同颜色的灯泡都是相连的，并且每一种颜色的灯泡个数都是相同的。Alice希望你能告诉她，总共有哪些方案呢？Alice是一个贪心的孩子，如果她发现方案不够多，或者太多了，就会很不高兴，于是她会尝试调整。对于编号为[b]x(x≠1)[/b]的灯泡，如果原来是挂在编号为[b]f[x][/b]的灯泡上，那么Alice会把第x个灯泡挂到[b]第 ( f[x] + 19940105 ) mod (x-1) + 1 个[/b]灯泡上。由于九在古汉语中表示极大的数，于是，[b][color=#FF0000]Alice决定只调整9次[/color][/b]。对于原始状态和每一次调整过的状态，Alice希望你依次告诉她每种状态下有哪些方案。 输入输出格式 输入格式：第一行一个整数n，表示灯泡的数量。接下来一行，有n-1个整数Ui，第i个数字表示第i+1个灯泡挂在了Ui个的下面。保证编号为1的灯泡是挂在天花板上的。数字之间用逗号（西文标点）" , "隔开且最后一个数字后面没有逗号。输出格式：对于10种状态下的方案，需要按照顺序依次输出。对于每一种状态，需要先输出单独的一行，表示状态编号，如样例所示。之后若干行，每行1个整数，表示划分方案中每种颜色的灯泡个数。[b]按升序输出。[/b]
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<vector> #include<cstring> using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;++i) #define lv(i,a,n) for(register int i = a;i >= n;--i) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) {char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-') op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op) x = -x; } template <class T> void write(T x) {if(x < 0) putchar('-'), x = -x;if(x >= 10) write(x / 10);putchar('0' + x % 10); } const int N = 2e6 + 5; int tot = 0,f[N],n,cnt[N],s[N]; vector <int> vec,ans; int main() {read(n);duke(i,2,n){read(f[i]);}duke(i,1,n){if(n % i == 0)vec.push_back(i);}int sum = vec.size() - 1;for(int cas = 1;cas <= 10;cas++){printf("Case #%d:\n",cas);ans.clear();duke(i,1,n)s[i] = 1;for(int i = n;i > 1;--i)s[f[i]] += s[i];clean(cnt);duke(i,1,n)cnt[s[i]]++;ans.push_back(1);duke(i,1,sum){tot = 0;for(int j = vec[i];j <= n;j += vec[i]){tot += cnt[j];}if(tot >= n / vec[i]) ans.push_back(vec[i]);}for(int i = 0;i < ans.size();++i){printf("%d\n",ans[i]);}for(int i = 2;i <= n;++i){f[i] = (f[i] + 19940105) % (i - 1) + 1;}}return 0; }