感觉自己还是很不擅长结论题啊。
先随便选一个树根，定义每一块中深度最小的点为这一块的根。
（可以发现选定了块的大小k后分块的方案就唯一确定了）
有一个显然的结论，一个点x能成为块根，仅当它的子树大小是k的倍数，即k|size[x]。
当且仅当满足此条件的点数有n/k个，k才对应一个合法方案。
先DFS求出size[],再枚举k统计答案即可。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 using namespace std; 5 6 const int N=1000010; 7 int n,u,v,ans,cnt,sz[N],sm[N],h[N],nxt[N<<1],to[N<<1]; 8 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } 9 10 void dfs(int x,int fa){ 11 sz[x]=1; 12 for (int i=h[x],k; i; i=nxt[i]) 13 if ((k=to[i])!=fa) dfs(k,x),sz[x]+=sz[k]; 14 } 15 16 int main(){ 17 freopen("bzoj4401.in","r",stdin); 18 freopen("bzoj4401.out","w",stdout); 19 scanf("%d",&n); 20 rep(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u); 21 dfs(1,0); rep(i,1,n) sm[sz[i]]++; 22 rep(i,1,n) if (!(n%i)){ 23 int tmp=0; 24 for (int j=i; j<=n; j+=i) tmp+=sm[j]; 25 if (tmp==n/i) ans++; 26 } 27 printf("%d ",ans); 28 return 0; 29 }