Description
小Y最近从同学那里听说了一个十分牛B的高级数据结构——块状树。听说这种数据结构能在sqrt(N)的时间内维护树上的各种信息,十分的高效。当然,无聊的小Y对这种事情毫无兴趣,只是对把树分块这个操作感到十分好奇。他想,假如能把一棵树分成几块,使得每个块中的点数都相同该有多优美啊!小Y很想知道,能有几种分割方法使得一棵树变得优美。小Y每次会画出一棵树,但由于手速太快,有时候小Y画出来的树会异常地庞大,令小Y感到十分的苦恼。但是小Y实在是太想知道答案了,于是他找到了你,一个天才的程序员,来帮助他完成这件事。
Input
第一行一个正整数N,表示这棵树的结点总数,接下来N-1行,每行两个数字X,Y表示编号为X的结点与编号为Y的结点相连。结点编号的范围为1-N且编号两两不同。
Output
一行一个整数Ans,表示所求的方案数。
Sample Input
1 2
2 3
2 4
4 5
5 6
Sample Output
HINT
100%的数据满足N<=1000000。
Solution
我竟然天真的以为$2e8$能跑过去直到我被最大的点卡到$10s$……
感觉也说不上什么算法,就算他是乱搞吧。
一开始洲哥给了一个$n\sqrt{n}$的写法。下一段根号做法可以不看因为我感觉我写的可能比正解还难懂……
我们先枚举当前要分的块大小$k$,再随便找一个根$DFS$一下,从下往上贪心的分,也就是够$k$个就分成一块。感性理解一下还是非常正确的……对于每个点$x$我们求出$(\sum size[son[x]]\%k)+1$,如果存在某个点的这个值大于$k$的话显然就是不合法的。其中$size[son[x]]\%k$也就是$son[x]$这颗子树里面分完了剩下的点。这个为什么是对的我就不多说了……要真想不懂的话可以直接去看下面正解做法。
其实仔细想想,确定了块大小$k$之后,那么每一块内的根的$size$肯定就是$k$的倍数。这个应该还是比较显然的,因为你是从下往上贪心来分的。那么我们直接开个桶记下$size$,对于每一个能被$n$整除的块大小$k$,统计有多少$size[x]$被$k$整除,如果与$n/k$相同则合法。复杂度应该是$O(n+\sqrt{n}logn)$
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#define N (1000009)
using namespace std; struct Edge{int to,next;}edge[N<<];
int n,ans,size[N],u,v,Keg[N];
int head[N],num_edge; inline int read()
{
int x=; char c=getchar();
while (c<'' || c>'') c=getchar();
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x;
} void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} void DFS(int x,int fa)
{
size[x]=;
for (int i=head[x]; i; i=edge[i].next)
if (edge[i].to!=fa)
{
DFS(edge[i].to,x);
size[x]+=size[edge[i].to];
}
Keg[size[x]]++;
} int main()
{
n=read();
for (int i=; i<=n-; ++i)
{
u=read(); v=read();
add(u,v); add(v,u);
}
DFS(,);
for (int i=; i<=n; ++i)
if (n%i==)
{
int sum=;
for (int j=; i*j<=n; ++j)
sum+=Keg[i*j];
ans+=(sum==n/i);
}
printf("%d\n",ans);
}
BZOJ4401:块的计数(乱搞)的更多相关文章
-
bzoj4401: 块的计数
首先,块的大小确定的话,可以发现方案最多只有1种 然后就可以O(nsqrt(n))搞,不过会TLE 接着我们又发现,一个节点可以作一个块的根,当且仅当该节点的size能被块的大小整除 然后就可以O(n ...
-
BZOJ4401: 块的计数 思维题
Description 小Y最近从同学那里听说了一个十分牛B的高级数据结构——块状树.听说这种数据结构能在sqrt(N)的时间内维护树上的各种信息,十分的高效.当然,无聊的小Y对这种事情毫无兴趣,只是 ...
-
【BZOJ4401/3004】块的计数/吊灯 乱搞
[BZOJ4401]块的计数 Description 小Y最近从同学那里听说了一个十分牛B的高级数据结构——块状树.听说这种数据结构能在sqrt(N)的时间内维护树上的各种信息,十分的高效.当然,无聊 ...
-
“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛题解&;&;源码【A,水,B,水,C,水,D,快速幂,E,优先队列,F,暴力,G,贪心+排序,H,STL乱搞,I,尼姆博弈,J,差分dp,K,二分+排序,L,矩阵快速幂,M,线段树区间更新+Lazy思想,N,超级快速幂+扩展欧里几德,O,BFS】
黑白图像直方图 发布时间: 2017年7月9日 18:30 最后更新: 2017年7月10日 21:08 时间限制: 1000ms 内存限制: 128M 描述 在一个矩形的灰度图像上,每个 ...
-
BZOJ_2801_[Poi2012]Minimalist Security_dfs树+特判+乱搞
BZOJ_2801_[Poi2012]Minimalist Security_dfs树+特判+乱搞 Description 给出一个N个顶点.M条边的无向图,边(u,v)有权值w(u,v),顶点i也有 ...
-
学渣乱搞系列之Tarjan模板合集
学渣乱搞系列之Tarjan模板合集 by 狂徒归来 一.求强连通子图 #include <iostream> #include <cstdio> #include <cs ...
-
URAL 1827 Indigenous Wars(排序、乱搞)
题意:给一个长度为n数组{a[i]}.有m个操作Ti,Si,Li表示找以Ti值结束,以Si值开始,长度为Li的连续子串.找到后,将区间的答案值设为1.一开始答案值全部为0.最后输出n个答案值. 好久没 ...
-
UVA 11853 [dfs乱搞]
/* 大连热身E题 不要低头,不要放弃,不要气馁,不要慌张 题意: 在1000×1000的格子内有很多个炮弹中心,半径给定. 为某人能否从西部边界出发,从东部边界走出. 不能输出不能,能的话输出最北边 ...
-
Codeforces 732e [贪心][stl乱搞]
/* 不要低头,不要放弃,不要气馁,不要慌张 题意: 给n个插座,m个电脑.每个插座都有一个电压,每个电脑都有需求电压. 每个插座可以接若干变压器,每个变压器可以使得电压变为x/2上取整. 有无限个变 ...
随机推荐
-
ActiveMQ结合Spring开发
---------------------------------------------------------------------------- Spring结合ActiveMQ开发 : 发送 ...
-
Linux下的压缩解压缩命令详解
linux zip命令zip -r myfile.zip ./*将当前目录下的所有文件和文件夹全部压缩成myfile.zip文件,-r表示递归压缩子目录下所有文件. 2.unzipunzip -o - ...
-
学习笔记day6:position index结合
z-index属性适用于定位元素(position 属性值为 relative 或 absolute 或 fixed的对象),用来确定定位元素在垂直于显示屏方向(称为Z轴)上的层叠顺序(stack o ...
-
ueditor 单独图片上传 转载
<body> <script type="text/javascript"> //这个是图片上传的,网上还有附件上传的 (function($) { var ...
- [置顶] vi、akw和sed总结
-
linux 安装 sftp
1,sftp:登陆命令 Xshell:\> sftp root@192.168.159.128 Connecting to 192.168.159.128:22... Connection es ...
-
【JavaScript中typeof、toString、instanceof、constructor与in】
JavaScript中typeof.toString.instanceof.constructor与in JavaScript 是一种弱类型或者说动态语言.这意味着你不用提前声明变量的类型,在程序运行 ...
-
Hi3516EV100烧录出厂固件
1.Hitool烧录uboot 2.uboot下烧录固件 setenv serverip 192.168.1.138 mw.b ff ;tftp ;sf probe ;sf erase ;sf wri ...
-
发送短信验证码倒计时,CountDownTimer;
1.声明CountDownTimer的成员变量: private CountDownTimer countDownTimer; 2.设置倒计时总时间和间隔时间: countDownTimer = ne ...
-
C# list.ForEach用法
list.ForEach(delegate(T model) { ... });