自动搬运

查看原文

来自洛谷，原作者为

	cyhzz **

搬运于2025-08-24 22:03:13，当前版本为作者最后更新于2019-04-24 20:07:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不错的思维题 7.5/10

假设你要切k条边，那么你会把这棵树切成k+1个连通块，每一块的大小为n/(k+1)，则k+1必定是n的约数

枚举约数？T了

任意选一个点为根，建树。假设你切掉了连接(fa[u],u)的一条边，那么u这棵子树大小必定是n/(k+1)的倍数。那我们找出满足子树大小等于n/(k+1)的倍数的点，若数量等于（k+1）那么一定可行。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=2010000;
int n,siz[MAXN],sum[MAXN],q[MAXN],ans;
int tot,front[MAXN],to[MAXN],nxt[MAXN];
void init(int u,int v)
{
	to[++tot]=v;
	nxt[tot]=front[u];
	front[u]=tot;
}
void dfs(int u,int father)
{
	siz[u]++;
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==father)continue;
		dfs(v,u);
		siz[u]+=siz[v];
	}
	sum[siz[u]]++;
}
bool check(int x)
{
	x++;
	if(n%x)return 0;
	int u=n/x,v=0;
	for(int i=u;i<=n;i+=u)v+=sum[i];
	return (v==x);
}
int main()
{
//	freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	scanf("%d",&n);
	for(int i=2,u,v;i<=n;i++)
	{
		scanf("%d%d",&u,&v);
		init(u,v);
		init(v,u);
	}
	dfs(1,0);
	for(int i=1;i<n;i++)
		if(check(i))
			q[++ans]=i;
	//printf("%d\n",ans);
	for(int i=1;i<=ans;i++)printf("%d ",q[i]);
	return 0;
}