【bzoj4401】块的计数 结论题
计数 结论
2023-09-11 14:22:39 时间
题目描述
给出一棵n个点的树,求有多少个si使得整棵树可以分为n/si个连通块。
输入
第一行一个正整数N,表示这棵树的结点总数,接下来N-1行,每行两个数字X,Y表示编号为X的结点与编号为Y的结点相连。结点编号的范围为1-N且编号两两不同。
输出
一行一个整数Ans,表示所求的方案数。
样例输入
6
1 2
2 3
2 4
4 5
5 6
样例输出
3
题解
结论题
结论:k可行当且仅当子树大小是k的倍数的节点数有n/k个。
这结论好像挺显然的(只要你能想出来。。。)
然后就做完了。。。先预处理出每个节点的size,对size维护桶,枚举n的约数,再枚举它的倍数求和统计即可。
时间复杂度为 $O(\sum\limits_{k|n}\frac nk=\sum\limits_{k|n}k=n\log\log n)$
#include <cstdio> #include <cctype> #define N 1000010 int head[N] , to[N << 1] , next[N << 1] , cnt , si[N] , v[N]; inline void add(int x , int y) { to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt; } void dfs(int x , int fa) { int i; si[x] = 1; for(i = head[x] ; i ; i = next[i]) if(to[i] != fa) dfs(to[i] , x) , si[x] += si[to[i]]; v[si[x]] ++ ; } inline char nc() { static char buf[100000] , *p1 , *p2; return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ; } inline int read() { int ret = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) ret = ((ret + (ret << 2)) << 1) + (ch ^ '0') , ch = nc(); return ret; } int main() { int n = read() , i , x , y , ans = 0; for(i = 1 ; i < n ; i ++ ) x = read() , y = read() , add(x , y) , add(y , x); dfs(1 , 0); for(i = 1 ; i <= n ; i ++ ) { if(!(n % i)) { for(x = 0 , y = i ; y <= n ; y += i) x += v[y]; if(x == n / i) ans ++ ; } } printf("%d\n" , ans); return 0; }
相关文章
- C语言程序设计100例之(58):连续子序列计数
- HDU 5304(Eastest Magical Day Seep Group's Summer-环加外向树生成树计数)[Template:Kirchhoff矩阵]
- 【BZOJ5305】[HAOI2018]苹果树(组合计数)
- 【BZOJ4818】序列计数(动态规划,生成函数)
- 【BZOJ4818】[Sdoi2017]序列计数 DP+矩阵乘法
- 对视频中的车辆进行计数,MATLAB仿真
- UVa 11401 Triangle Counting (计数DP)
- std::shared_ptr 和 std::weak_ptr的用法以及引用计数的循环引用问题
- 《Android游戏开发详解》一2.7 构建一个简单的计数程序
- PySpark 教程之 Count(1) vs Count(*) vs Count(col_name),那个是正确的方式从表中获取计数
- 力扣解法汇总2283. 判断一个数的数字计数是否等于数位的值
- 《Storm分布式实时计算模式》——第1章 分布式单词计数1.1 Storm topology的组成部分——stream、spout和bolt
- 【cf789D】Weird journey(欧拉路、计数)
- 【HDU 4408】Minimum Spanning Tree(最小生成树计数)
- Unity 工具 之 简单引用计数器的封装整理,继承即可使用,便于简单计数使用及相关计算事件触发
- 【opencv】——钢管计数(霍夫圆变换 + 阈值 + canny)
- [DAX] 计数函数