题目链接:Justified Jungle
显然可以割点边数+1,一定是n的因子。
然后枚举n的因子,比如当前 x+1是n的因子。
那么割 x 条边,剩下 (x+1) 个连通块,且大小为 n/(x+1) ,所以我们树的子树size为 n/(x+1) 的个数一定要有x+1个。
AC代码:
#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=1e6+10;int n,sz[N],cnt[N];vector<int> g[N];inline void add(int a,int b){g[a].push_back(b),g[b].push_back(a);}void dfs(int x,int fa) {sz[x]=1;for(auto to:g[x])if(to!=fa)dfs(to,x),sz[x]+=sz[to];cnt[sz[x]]++;}inline int check(int x) {if(n%x)return 0;int tmp=0,w=n/x;for(int i=w; i<=n; i+=w)tmp+=cnt[i];return tmp>=x;}signed main() {cin>>n;for(int i=1,a,b; i<n; i++)scanf("%d %d",&a,&b),add(a,b);dfs(1,1);for(int i=1; i<n; i++)if(check(i+1))printf("%d ",i);return 0;}
如果觉得《Justified Jungle》对你有帮助,请点赞、收藏,并留下你的观点哦!