BZOJ4401:块的计数(乱搞)

时间:2021-09-22 20:24:33

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

6
1 2
2 3
2 4
4 5
5 6

Sample Output

3

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:块的计数(乱搞)的更多相关文章

  1. bzoj4401&colon; 块的计数

    首先,块的大小确定的话,可以发现方案最多只有1种 然后就可以O(nsqrt(n))搞,不过会TLE 接着我们又发现,一个节点可以作一个块的根,当且仅当该节点的size能被块的大小整除 然后就可以O(n ...

  2. BZOJ4401&colon; 块的计数 思维题

    Description 小Y最近从同学那里听说了一个十分牛B的高级数据结构——块状树.听说这种数据结构能在sqrt(N)的时间内维护树上的各种信息,十分的高效.当然,无聊的小Y对这种事情毫无兴趣,只是 ...

  3. 【BZOJ4401&sol;3004】块的计数&sol;吊灯 乱搞

    [BZOJ4401]块的计数 Description 小Y最近从同学那里听说了一个十分牛B的高级数据结构——块状树.听说这种数据结构能在sqrt(N)的时间内维护树上的各种信息,十分的高效.当然,无聊 ...

  4. &OpenCurlyDoubleQuote;盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛题解&amp&semi;&amp&semi;源码【A&comma;水&comma;B&comma;水&comma;C&comma;水&comma;D&comma;快速幂&comma;E&comma;优先队列&comma;F&comma;暴力&comma;G&comma;贪心&plus;排序&comma;H&comma;STL乱搞&comma;I&comma;尼姆博弈&comma;J&comma;差分dp&comma;K&comma;二分&plus;排序&comma;L&comma;矩阵快速幂&comma;M&comma;线段树区间更新&plus;Lazy思想&comma;N&comma;超级快速幂&plus;扩展欧里几德&comma;O&comma;BFS】

    黑白图像直方图 发布时间: 2017年7月9日 18:30   最后更新: 2017年7月10日 21:08   时间限制: 1000ms   内存限制: 128M 描述 在一个矩形的灰度图像上,每个 ...

  5. BZOJ&lowbar;2801&lowbar;&lbrack;Poi2012&rsqb;Minimalist Security&lowbar;dfs树&plus;特判&plus;乱搞

    BZOJ_2801_[Poi2012]Minimalist Security_dfs树+特判+乱搞 Description 给出一个N个顶点.M条边的无向图,边(u,v)有权值w(u,v),顶点i也有 ...

  6. 学渣乱搞系列之Tarjan模板合集

    学渣乱搞系列之Tarjan模板合集 by 狂徒归来 一.求强连通子图 #include <iostream> #include <cstdio> #include <cs ...

  7. URAL 1827 Indigenous Wars(排序、乱搞)

    题意:给一个长度为n数组{a[i]}.有m个操作Ti,Si,Li表示找以Ti值结束,以Si值开始,长度为Li的连续子串.找到后,将区间的答案值设为1.一开始答案值全部为0.最后输出n个答案值. 好久没 ...

  8. UVA 11853 &lbrack;dfs乱搞&rsqb;

    /* 大连热身E题 不要低头,不要放弃,不要气馁,不要慌张 题意: 在1000×1000的格子内有很多个炮弹中心,半径给定. 为某人能否从西部边界出发,从东部边界走出. 不能输出不能,能的话输出最北边 ...

  9. Codeforces 732e &lbrack;贪心&rsqb;&lbrack;stl乱搞&rsqb;

    /* 不要低头,不要放弃,不要气馁,不要慌张 题意: 给n个插座,m个电脑.每个插座都有一个电压,每个电脑都有需求电压. 每个插座可以接若干变压器,每个变压器可以使得电压变为x/2上取整. 有无限个变 ...

随机推荐

  1. ActiveMQ结合Spring开发

    ---------------------------------------------------------------------------- Spring结合ActiveMQ开发 : 发送 ...

  2. Linux下的压缩解压缩命令详解

    linux zip命令zip -r myfile.zip ./*将当前目录下的所有文件和文件夹全部压缩成myfile.zip文件,-r表示递归压缩子目录下所有文件. 2.unzipunzip -o - ...

  3. 学习笔记day6:position index结合

    z-index属性适用于定位元素(position 属性值为 relative 或 absolute 或 fixed的对象),用来确定定位元素在垂直于显示屏方向(称为Z轴)上的层叠顺序(stack o ...

  4. ueditor 单独图片上传 转载

    <body> <script type="text/javascript"> //这个是图片上传的,网上还有附件上传的 (function($) { var ...

  5. &lbrack;置顶&rsqb; vi、akw和sed总结

  6. linux 安装 sftp

    1,sftp:登陆命令 Xshell:\> sftp root@192.168.159.128 Connecting to 192.168.159.128:22... Connection es ...

  7. 【JavaScript中typeof、toString、instanceof、constructor与in】

    JavaScript中typeof.toString.instanceof.constructor与in JavaScript 是一种弱类型或者说动态语言.这意味着你不用提前声明变量的类型,在程序运行 ...

  8. Hi3516EV100烧录出厂固件

    1.Hitool烧录uboot 2.uboot下烧录固件 setenv serverip 192.168.1.138 mw.b ff ;tftp ;sf probe ;sf erase ;sf wri ...

  9. 发送短信验证码倒计时,CountDownTimer;

    1.声明CountDownTimer的成员变量: private CountDownTimer countDownTimer; 2.设置倒计时总时间和间隔时间: countDownTimer = ne ...

  10. C&num; list&period;ForEach用法

    list.ForEach(delegate(T model) { ... });