题解 P4748 【[CERC2017]Justified Jungle】

· · 题解

不错的思维题 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;
}