P2351 [SDOI2012] 吊灯

考虑对于一个大小 \(x\) 如何判断是否合法。
有结论：子树大小是 \(x\) 的倍数的点的数量一定要是 \(\frac nx\)。
规定：称 “子树大小是 \(x\) 的倍数的点”为 \(A\) 类点。

必要性

首先，如果 \(A\) 类点的数量小于 \(\frac nx\)，那么一定不可能。使用反证法，如果存在一种方案满足条件，那么把所有颜色深度最小的点拿出来，会发现祂们都是 \(A\) 类点，这样就有 \(\frac nx\) 个 \(A\) 类点了，矛盾。
如果 \(A\) 类点的数量大于 \(\frac nx\)，那么也不可能。对于两个 \(A\) 类点，祂们的子树要么一个包含另一个，要么不相交。对于每个点，把祂子树内所有 \(A\) 类点的子树全部删掉，剩下的点的个数一定还是 \(x\) 的倍数。假设 \(A\) 类点的数量为 \(k\)，那么我们就得到了 \(k\) 个大小至少为 \(x\) 的联通块，最少共有 \(x\times k\) 个点。如果 \(k>\frac nx\)，点数就大于 \(n\) 了，所以不可能。

充分性

对于一个 \(A\) 类点 \(u\)，以祂为根 \(dfs\)，遇到其他 \(A\) 类点就返回，否则把遇到的点染成和 \(u\) 一样的颜色这样我们就得到了一个合法的染色方案。

代码

结论有了，代码就很好写了。
注意：如果要存图，不能用 \(vector\)，要用链式前向星，或者直接倒着便利。
时间复杂度 \(\mathcal O(n\log\log n)\)，还有个 \(10\) 被常数。

/*
Luogu P2351 [SDOI2012] 吊灯
2026-03-23
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int maxn,int maxm>class LSQXX{
public:
    int head[maxn],nxt[maxm*2],to[maxm*2],cnt=0;
    void add(int u,int v){nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt;}
    void clear(){cnt=0;memset(head,0,sizeof(head));}
};
const int maxn=1200010;
LSQXX<maxn,maxn>e;
int n,fa[maxn],g[maxn],sz[maxn];
void solve(){
    for(int i=1;i<=n;i++) g[i]=0,sz[i]=1;
    for(int i=n;i>1;i--) sz[fa[i]]+=sz[i]; 
    for(int i=1;i<=n;i++) g[sz[i]]++;
    for(int i=1;i<=n;i++){
        if(n%i) continue;
        int gs=0;
        for(int j=i;j<=n;j+=i) gs+=g[j];
        if(gs==n/i) write(i),write("\n");
    }
}
void change(){for(int i=2;i<=n;i++) fa[i]=(fa[i]+19940105)%(i-1)+1;}
signed main(){
    read(n);
    for(int i=2;i<=n;i++) read(fa[i]);
    for(int c=1;c<=10;c++) write("Case #"),write(c),write(":\n"),solve(),change();
    return 0;
}