「题解」GYM 101620J Justified Jungle

令 (t=k+1)，枚举 (t)，最多只有 (d(n)) 个，随便钦点一个为根，每个子树的大小都是 (c=frac{n}{t})，易得充要条件为 (size) 为 (c) 倍数的树的个数 (geq t)．

(Rightarrow)：对于所有分出来的连通块，其 (dep) 最小的节点 (size) 一定是 (c) 的倍数，所以 (size) 为 (c) 倍数的树的个数 (geq t)．

(Leftarrow)：构造，对于每次把 (size=c) 的子树删除，然后更新其它点的 (size)．这种构造是始终存在的，即不会出现树未删完并且不存在这样的子树的情况。证明考虑同样的删法，每次把子树中不存在 (size) 为 (c) 的倍数且自己的 (size) 为 (c) 的倍数的子树删掉，删的总次数一定 (<t)，与假设矛盾。

实现上采用狄里克雷后缀和，时间复杂度可以到 (mathcal{O}(nlog log n))．

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
const ll mod = 998244353;
ll Add(ll x, ll y) { return (x+y>=mod) ? (x+y-mod) : (x+y); }
ll Mul(ll x, ll y) { return x * y % mod; }
ll Mod(ll x) { return x < 0 ? (x + mod) : (x >= mod ? (x-mod) : x); }
ll cadd(ll &x, ll y) { return x = (x+y>=mod) ? (x+y-mod) : (x+y); }
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T>
T &read(T &r) {
	r = 0; bool w = 0; char ch = getchar();
	while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
	while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
	return r = w ? -r : r;
}
const int N = 1000100;
int n, a[N], siz[N], p[N], pct;
bool vis[N];
void pre() {
	vis[1] = 1;
	for(int i = 2; i <= n; ++i) {
		if(!vis[i]) p[++pct] = i;
		for(int j = 1; j <= pct && i * p[j] <= n; ++j) {
			vis[i*p[j]] = 1;
			if(i%p[j] == 0) break ;
		}
	}
}
vi eg[N];
void dfs(int x, int f) {
	siz[x] = 1;
	for(auto v : eg[x])
		if(v != f) {
			dfs(v, x);
			siz[x] += siz[v];
		}
	a[siz[x]]++;
}
signed main() {
	read(n); pre();
	for(int i = 1; i < n; ++i) {
		int x, y; read(x); read(y);
		eg[x].pb(y); eg[y].pb(x);
	}
	dfs(1, 0);
	for(int i = 1; i <= pct; ++i)
		for(int j = n/p[i]; j; --j)
			a[j] += a[j*p[i]];
	vi ans;
	for(int i = 2; i <= n; ++i)
		if(n % i == 0 && a[n/i] >= i)
			printf("%d ", i-1);
	return 0;
}