题目描述
李华终于逃离了无尽的英语作文，重获自由的他对一棵树产生了兴趣。
首先，他想知道一棵树是否能分成大小相同的几块（即切掉一些边，使得每个连通块的点数相同）。然后，他觉得这个问题过于简单，于是他想知道一共有多少种方案可以把这棵树分成大小相同的几块。
然后他发现自己不会了，于是向聪明的你求助。
输入格式
第一行一个数，表示数的大小。
第二行至第$N$行，每行两个数$x,y$表示$x$和$y$之间有一条边。
输出格式
一行，表示方案数。
样例
样例输入
6
1 2
2 3
2 4
4 5
5 6
样例输出
3
数据范围与提示
对于$30\%$的数据，$1leqslant nleqslant 100$。
对于$60\%$的数据，$1leqslant nleqslant 100,000$。
对于$100\%$的数据，$1leqslant nleqslant 1,000,000$。
题解
首先，块的大小和块的个数一定能整除$N$，所以我们可以先预处理出来所有$N$的因子。
然后我们来考虑如何判断方案是否可行，显然只有一棵子树的大小是当前尝试块的大小或其整数倍才可以，那么问题就简单多了。
但是这时候，你可能会发现，时间复杂度还是可怕的$Theta(nsqrt n)$，虽然同桌随机化根在交了$5,6,7,8,9,10$遍后还是$A$了这道题吧。
当然我们不能当像他一样的颓狗
那么应该怎么办呢？
考虑在搜索的时候如何进行剪枝，可以先预处理出来每棵子树的大小，如果当前这棵子树的大小恰好等于块的大小我们那就可以将其剪掉，如果它没有块大，那么记录还差多少，看是否可行，如果它比块大，那么就接着往下搜。
时间复杂度：$Theta(nsqrt n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
struct rec
{
int nxt;
int to;
}e[3000000];
int head[1000010],cnt;
int n;
int ans=2;
int que[1000],size[1000010],fa[1000010];
void add(register int x,register int y)
{
e[++cnt].nxt=head[x];
e[cnt].to=y;
head[x]=cnt;
}
void pre_dfs(register int x)
{
size[x]++;
for(register int i=head[x];i;i=e[i].nxt)
if(e[i].to!=fa[x])
{
fa[e[i].to]=x;
pre_dfs(e[i].to);
size[x]+=size[e[i].to];
}
}
int judge(register int x,register int w)
{
register int sz=1;
for(register int i=head[x];i;i=e[i].nxt)
{
if(e[i].to==fa[x])continue;
if(size[e[i].to]>=w)
{
register int flag=judge(e[i].to,w);
if(flag==-1)return -1;
sz+=flag;
}
else sz+=size[e[i].to];
if(sz>w)return -1;
}
if(sz==w)return 0;
return sz;
}
int main()
{
register int n;
scanf("%d",&n);
for(register int i=2;i<n;i++)
if(!(n%i))que[++que[0]]=i;
for(register int i=1;i<n;i++)
{
register int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
pre_dfs(1);
for(register int i=1;i<=que[0];i++)
if(judge(1,que[i])!=-1)ans++;
cout<<ans<<endl;
return 0;
}
rp++