P2351 [SDOI2012]吊灯

Hehe_0 · 2021-08-07 15:57:49 · 题解

大致题意：我们需要在一个树上改变9次树的形态（有固定规则，题面已给出，可详见代码），每次我们需要使相同颜色相连（分组），每个联通块大小相等。求每种形态树满足要求的组大小。

显然，我们的这个数一定是总结点的约数。
我们可以考虑去找每个块的大小，比如为 x
注意：一定存在 \left ( \dfrac { n }{x} \right ) 其子树大小为 x 的倍数。

我们可以很暴力的枚举 1~n ，看：1 . 它是不是约数 2 .放 到树上是否可行

每次枚举后树的形态都会改变，记得重新处理 siz ， num

#include<bits/stdc++.h>

using namespace std;
const int N=12e5+7;

int fa[N],siz[N],num[N];
int n;
inline int read()
{
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
    while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
    return out * flag;
}
void init()
{
    fill(num,num+1+n,0);
    fill(siz,siz+1+n,1);
    for(int i=n;i;i--)
    {
        siz[fa[i]]+=siz[i];
        num[siz[i]]++;
    }
    return ;
}
bool pd(int x)
{
    int re=0;
    for(int i=x;i<=n;i+=x)
    {//x的倍数大小的数量 
        re+=num[i];
    }
    return re==n/x;
}

int main()
{
    ios::sync_with_stdio(false);
    n=read();

    for(int i=2;i<=n;i++)
    fa[i]=read();

    for(int cas=1;cas<=10;cas++)
    {
        cout<<"Case #"<<cas<<':'<<endl; 
        init();

        for(int i=1;i<=n;i++)
        {
            if((!(n%i))&&pd(i))
            cout<<i<<endl;
        }

        for(int i=2;i<=n;i++)
        fa[i]=(fa[i]+19940105)%(i-1)+1;
    }

    return 0;
}