Description
Alice家里有一盏很大的吊灯。所谓吊灯，就是由很多个灯泡组成。只有一个灯泡是挂在天花板上的，剩下的灯泡都是挂在其他的灯泡上的。也就是说，整个吊灯实际上类似于一棵树。其中编号为1的灯泡是挂在天花板上的，剩下的灯泡都是挂在编号小于自己的灯泡上的。
现在，Alice想要办一场派对，她想改造一下这盏吊灯，将灯泡换成不同的颜色。她希望相同颜色的灯泡都是相连的，并且每一种颜色的灯泡个数都是相同的。
Alice希望你能告诉她，总共有哪些方案呢？
Alice是一个贪心的孩子，如果她发现方案不够多，或者太多了，就会很不高兴，于是她会尝试调整。对于编号为x(x≠1)的灯泡，如果原来是挂在编号为f[x]的灯泡上，那么Alice会把第x个灯泡挂到第 ( f[x] + 19940105 ) mod (x-1) + 1 个灯泡上。
由于九在古汉语中表示极大的数，于是，Alice决定只调整9次。对于原始状态和每一次调整过的状态，Alice希望你依次告诉她每种状态下有哪些方案。
对于100%的数据，n<=1.2*106。
/**************************************************************
Problem: 3004
User: ictsing
Language: C++
Result: Accepted
Time:3340 ms
Memory:18868 kb
****************************************************************/
//SD2012_DAY1_divide_std_100
/*
再理一遍思路，
要求重构10次树（强行修改f[x]）
强行加边
然后题目要求颜色相同，
其实就是把树分成n/k块相等的块。
如何解决此类问题：
暴力删除（显然从树底删除起）
有没有更快的方法？
首先有一个性质：
当某个k满足条件的时候，要求有正好n/k个根的子树大小为k
证明其充分性：
模拟删除
证明其必要性：
显然
首先不可能存在超过n／k个节点满足以每个节点为根的子树大小都是k的倍数，这是废话
首先证明必要性：
假设我们已经有了一组合法的方案，那么对于每一个连通块，我们找到这个连通块中深度最小的节点，以这个节点为根的子树大小一定是k的倍数
由于这样的节点有n／k个，因此必要性得证
下面来证明充分性：
假设现在我们已经找到了n／k个节点满足以每个节点为根的子树大小都是k的倍数，那么：
首先我们从根节点出发开始DFS，每遇到一个节点满足以这个节点为根的子树大小是k的倍数，就把这个节点为根的子树砍掉
这样做之后，我们得到了一个连通块和一些子树，其中连通块的大小为k的倍数，且除根节点外其余n/k−1个节点都在那些子树中
对每个子树重复这一操作，一定能得到一组合法的方案
因此充分性得证
注意细节问题：
dfs求sz会TLE
直接sz[f[x]]+=(++sz[x]);即可
qaq[i]表示子树大小为i的个数即可统计
「当某个k满足条件的时候，要求有正好n/k个根的子树大小为k」
读数字的时候直接读就好了，不然会出现奇奇怪怪的错误，比如RE||WA
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mt =1.5*1e6+5;
//char s[mt<<1];
int n;
int f[mt],sz[mt],qaq[mt];
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
void adjust()
{
for(int i=2;i<=n;i++)
f[i]=(f[i]+19940105)%(i-1)+1;
}
int main()
{
n=read();
//scanf("%s",s+1);
//for(int i=2;i<=n*2-1;i+=2)
//f[i/2+1]=s[i-1]-'0';
for(int i=2;i<=n;i++)
f[i]=read();
int cnt=0;
while(cnt<=9)
{
cnt++;
printf("Case #%d:\n",cnt);
puts("1");
memset(sz,0,sizeof(sz));
memset(qaq,0,sizeof(qaq));
for(int i=n;i>=1;i--)
sz[f[i]]+=(++sz[i]);
for(int i=1;i<=n;i++)
qaq[sz[i]]++;
for(int k=2;k<n;k++)
if(n%k==0)
{
int tmp=0;
for(int i=1;i<=n/k;i++)
tmp+=qaq[i*k];
if(tmp==n/k) printf("%d\n",k);
}
printf("%d\n",n);
adjust();
}
return 0;
}
评论