1s    256M

这题的解法好巧妙。

我们可以通过dfs来处理一个 f 数组。f[i]表示以i为根的子树有多少个节点。

那么当我们从1到n枚举每个块的大小时（n%i==0），然后扫一遍 f 数组，f[]为 i 的倍数的个数如果等于n/i，那么就是一种成功的方案。

#include
     
      #include
      
       #include
       
        #define LL long long#define N 1000009using namespace std;int n,ans;int head[N],nxt[2*N],to[2*N],cnt;int f[N];//记录以i为根的子树有多少个节点 bool vis[N];void add(int x,int y){    to[++cnt]=y;    nxt[cnt]=head[x];    head[x]=cnt;}int dfs(int x){    vis[x]=1;    int tot=0;    for(int i=head[x];i;i=nxt[i])    {        if(!vis[to[i]])         {            vis[to[i]]=1;            tot+=f[to[i]]?f[to[i]]:f[to[i]]=dfs(to[i]);        }    }    return tot+1;}bool check(int x){    int tot=0;    for(int i=1;i<=n;i++)    if(f[i]%x==0) tot++;    return tot==(n/x);}int main(){    scanf("%d",&n);    for(int i=1;i