BZOJ 4401 块的计数


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

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


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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4401 块的计数


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: