BZOJ 4401 块的计数

发布于 2017-09-08  127 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4401

题意:一棵树能划分成哪些大小相等的连通块,输出不同的方案数。


怎么又是这种 狗题 ....

略有不同之处是我们还需要证明一个事情:确定块大小后划分方案唯一... 其实随便 YY 下就好了。

我口胡下:
考虑包含叶子节点且叶子节点深度最大的那个连通块,尝试在这个连通块附近构造另一种划分方案。首先连通块内深度最深的点肯定不能动... 因为它下面没有足够多的点构造另一个连通块了... 对于这个连通块内深度最大的点,可以向上爬,不过必须爬出一个连通块大小那么多的点才能让下面的点能划分到一个连通块内。而如果这么做就相当于交换了两个相邻的连通块... 所以包含叶子节点且叶子节点深度最大的那个连通块的固定的,可以切掉它。这样考虑下去整个树就切完了...

 


一个非常弱的准退役OIER