JZOJ 4757. 树上摩托

Description

Sherco是一位经验丰富的魔♂法师。
Sherco在第零次圣杯战争中取得了胜利,并取得了王之宝藏——王の树。
他想把这棵树砍去任意条边，拆成若干棵新树，并装饰在他的摩托上，让他的摩托更加酷炫。
但Sherco认为，这样生成的树不具有美感，于是Sherco想让每棵新树的节点数相同。
他想知道有多少种方法分割这棵树。

Input

第一行一个正整数N，表示这棵树的结点总数。
接下来N-1行，每行两个数字X，Y表示编号为X的结点与编号为Y的结点相连。结点编号的范围为[1,N]。

Output

一个整数，表示方案数。注意，不砍去任何一条边也算作一种方案。

Sample Input

6
1 2
2 3
2 4
4 5
5 6

Sample Output

3

Data Constraint

对于40%的数据，N ≤ 15
对于60%的数据，N ≤ 10^5
对于100%的数据，N ≤ 10^6
数据规模非常大，请使用高效的读入方式。

 

做法：强行选定一个根，然后求出每个节点size的大小，当新子树大小确定时，只有一种方案，所以我们可以枚举新子树大小k，当所有节点中size值是k的倍数的节点数为n/k时，方案合法。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #define N 1000007

 using namespace std;

 int n,tot,list[N],size[N],fa[N],b[N],ans,ls[N];

 struct edge{

     int to,next;

 }e[N*];

 bool v[N];

 inline int Read(){

     int s=;

     char ch=getchar();

     for(;ch<''||ch>'';ch=getchar());

     for(;ch>=''&&ch<='';s=s*+ch-'',ch=getchar());

     return s;

 }

 inline void Add(int x,int y){

     e[++tot].to=y;

     e[tot].next=ls[x];

     ls[x]=tot;

 }

 void Init(){

     n=Read();

     for (int i=;i<n;i++){

         int x=Read(),y=Read();

         Add(x,y),Add(y,x);

     }

 }

 void Bfs(){

     int h=,t=;

     list[++t]=;

     v[]=;

     for(;h<t;){

         h++;

         int now=list[h];

         for (int i=ls[now];i;i=e[i].next){

             if (v[e[i].to]) continue;

             fa[e[i].to]=now;

             list[++t]=e[i].to;

             v[e[i].to]=;

         }

     }

 }

 void Calc_son(){

     for (int i=;i<=n;i++) size[i]=;

     for (int i=n;i>=;i--) size[fa[list[i]]]+=size[list[i]];

     for (int i=;i<=n;i++) b[size[i]]++;

 }

 int main(){

     Init();

     Bfs();

     Calc_son();

     for (int i=;i<=n;i++){

         if (n%i) continue;

         int k=;

         for (int j=;j<=n/i;j++)

             k+=b[i*j];

         if (k==n/i) ans++;

     }

     printf("%d",ans);

 }