BZOJ 3391 [Usaco2004 Dec]Tree Cutting 网络破坏

发布于 2017-06-12  97 次阅读


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

题意:一棵树,切掉一个点,使得剩下的联通块最大不超过树大小的一半,问哪些点可以切...


大水题... 然而做了 20min...

dfs 处理子树大小,对于切的每一个点,若它子树有大小超过 mid 的或者 n-以自身为根的子树大小超过 mid 则不可以切

 


一个非常弱的准退役OIER