【结论】BZOJ4401 块的计数

题面在这里

​

• 只有n的因子能作为块的大小
• 块大小确定的情况下，至多有一种划分方法
• 块大小为\(d\)时，存在一种划分方法当且仅当有\(\frac n d\)个子树的大小被\(d\)整除

前两条的正确性显然

对于第三条，考虑如果有划分方法，把根所在的块去掉，剩下几个子树大小一定都被\(d\)整除，以此类推

​

示例程序：

#include<cstdio>
inline char nc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
	int res=0,f=1;char ch=nc();
	while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
	while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
	return res*f;
}

const int maxn=1000005,maxe=2000005;
int n,siz[maxn],s[maxn];
int tot,son[maxe],nxt[maxe],lnk[maxn];
inline void add(int x,int y){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
void dfs(int x,int fa){
	siz[x]=1;
	for (int j=lnk[x];j;j=nxt[j])
	 if (son[j]!=fa){
	 	dfs(son[j],x); siz[x]+=siz[son[j]];
	 }
}
bool check(int x){
	int tot=0;
	for (int i=x;i<=n;i+=x) tot+=s[i];
	return tot==n/x;
}
int main(){
	n=red();
	for (int i=1,x,y;i<n;i++) x=red(),y=red(),add(x,y),add(y,x);
	dfs(1,1);
	for (int i=1;i<=n;i++) s[siz[i]]++;
	int ans=0;
	for (int d=1;d*d<=n;d++)
	 if (n%d==0){
	 	if (check(d)) ans++;
	 	if (d*d!=n&&check(n/d)) ans++;
	 }
	printf("%d",ans);
	return 0;
}