这题比较神。。 首先我不会做 一开始想的是先暴力枚举块的大小，然后暴力构一次，看行不行 话说有个结论哈，就是说对于同一个块的大小，只有一种构造方法 至于怎么证，我也没有认真地证过。。 我大概的想法就是从叶子节点开始证，接着分类讨论一下，反正我没有证。。 然而这种方法是 nn√ ，很明显不可以过。。 当然，要是数据水的话就不一定了 然后我就不会了
于是就看了题解。。 发现了很强的东西（以下来自http://blog.csdn.net/werkeytom_ftd/article/details/53105852）
我们发现，我们会在那些原本的size（这里的size指子树大小）就是c的倍数的地方划分出新的一块。 大概意思就是，我们设s[x]表示size[x]%c。 那么我删除一个子树y满足s[y]=0而且子树y内所有除y节点s均不为0，接下来整颗树其余未删除部分的s仍然不变吧？ 而回忆TLE算法，每删一次就意味着分出了一块。所以如果要分块成功，我们需要分出恰好n/c个块，也就是意味s值为0的节点要有n/c个，那么就是说——size是c的倍数的节点要有n/c个！ 我们开个桶记录每种size的节点个数，枚举块大小c，然后去暴力计算其倍数size的个数，这样是n log n的。
然后就可以做了。。 看来我还是太菜了QAQ 要是比赛遇到这题，估计 nn√ 也可以有30分。。【满足】
#include<cstdio> #include<cstring> const int N=1000005; int n; struct qq { int x,y,last; }e[N*2];int num,last[N]; void init (int x,int y) { num++; e[num].x=x;e[num].y=y; e[num].last=last[x]; last[x]=num; } int tot[N]; int sum[N]; void dfs (int x,int fa) { tot[x]=1; for (int u=last[x];u!=-1;u=e[u].last) { int y=e[u].y; if (y==fa) continue; dfs(y,x); tot[x]=tot[x]+tot[y]; } sum[tot[x]]++; } int main() { memset(sum,0,sizeof(sum)); num=0;memset(last,-1,sizeof(last)); scanf("%d",&n); for (int u=1;u<n;u++) { int x,y; scanf("%d%d",&x,&y); init(x,y);init(y,x); } int ans=0; dfs(1,0); for (int u=1;u<=n;u++) { if (n%u==0) { int lalal=0; for (int i=u;i<=n;i+=u) lalal=lalal+sum[i]; if (lalal==n/u) ans++; } } printf("%d\n",ans); return 0; }