【bzoj4401】块的计数

首先，块的大小确定的话，可以发现方案最多只有1种

然后就可以O(nsqrt(n))搞，不过会TLE

接着我们又发现，一个节点可以作一个块的根，当且仅当该节点的size能被块的大小整除

然后就可以O(nlogn)搞了

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

#define N 1000010

struct edge

{

    int to,next;

}e[N<<1];

int head[N<<1];

int cnt;

int n;

int x,y;

int ans;

int f[N],p[N];

void link(int x,int y)

{

    e[++cnt]=(edge){y,head[x]};

    head[x]=cnt;

}

void dfs(int x,int d)

{

    f[x]=1;

    for (int i=head[x];i;i=e[i].next)

        if (e[i].to!=d)

        {

            dfs(e[i].to,x);

            f[x]+=f[e[i].to];

        }

    p[f[x]]++;

}

int main()

{

    scanf("%d",&n);

    for (int i=1;i<n;i++)

        scanf("%d%d",&x,&y),link(x,y),link(y,x);

    dfs(1,0);

    for (int i=1;i<=n;i++)

    {

        for (int j=i<<1;j<=n;j+=i)

            p[i]+=p[j];

        if (i*p[i]==n)

            ans++;

    }

    printf("%d",ans);

    return 0;

}