根据块状树的那堆理论可以发现，对于某种块大小，可行的分法只有一种
如果一个点能被当成块顶，仅当其子树大小是块大小的倍数
于是枚举块的大小\(i\)，当可行的块顶个数大于等于\(n / i\)时，就可以构造出可行的分法了
时间复杂度 \(O(\sum_{d|n}d)\)
#include <bits/stdc++.h> #define N 2010000 using namespace std; int n; int lt[N], bi[N], nt[N], tl; int si[N], ai[N]; void dfs(int t, int f) { si[t] = 1; for (int i = lt[t]; i; i = nt[i]) if (bi[i] != f) dfs(bi[i], t), si[t] += si[bi[i]]; ai[si[t]] ++; } int ans; int main() { scanf("%d", &n); for (int i = 1; i < n; ++ i) { int x, y; scanf("%d%d", &x, &y); nt[++ tl] = lt[x]; lt[x] = tl; bi[tl] = y; nt[++ tl] = lt[y]; lt[y] = tl; bi[tl] = x; } dfs(1, 0); for (int i = 1; i <= n; ++ i) if (n % i == 0) { int cnt = 0; for (int j = i; j <= n; j += i) cnt += ai[j]; if (cnt >= n / i) ans ++; } printf("%d", ans); }
原文：http://www.cnblogs.com/AwD-/p/6290930.html