首页 > 代码库 > bzoj 4401: 块的计数
bzoj 4401: 块的计数
根据块状树的那堆理论可以发现，对于某种块大小，可行的分法只有一种
如果一个点能被当成块顶，仅当其子树大小是块大小的倍数
于是枚举块的大小\(i\)，当可行的块顶个数大于等于\(n / i\)时，就可以构造出可行的分法了
时间复杂度 \(O(\sum_{d|n}d)\)
#include <bits/stdc++.h>#define N 2010000using namespace std;int n;int lt[N], bi[N], nt[N], tl;int si[N], ai[N];void dfs(int t, int f){ si[t] = 1; for (int i = lt[t]; i; i = nt[i]) if (bi[i] != f) dfs(bi[i], t), si[t] += si[bi[i]]; ai[si[t]] ++;}int ans;int main(){ scanf("%d", &n); for (int i = 1; i < n; ++ i) { int x, y; scanf("%d%d", &x, &y); nt[++ tl] = lt[x]; lt[x] = tl; bi[tl] = y; nt[++ tl] = lt[y]; lt[y] = tl; bi[tl] = x; } dfs(1, 0); for (int i = 1; i <= n; ++ i) if (n % i == 0) { int cnt = 0; for (int j = i; j <= n; j += i) cnt += ai[j]; if (cnt >= n / i) ans ++; } printf("%d", ans);}
bzoj 4401: 块的计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。