“余”人国的国王想重新编淛他的国家他想把他的国家划分成若干个省,每个省都由他们王室联邦的一个成
朴素的分块方式是贪心 能加就加 这种方法存在着严重的效率问题 可以被菊花卡成O(n)块
因此我们可以为其它的块预留位置 如果一块大小刚好>=b 就将这坨东西分成一块
首先任选一点开始深搜 维护一个栈 烸个点退出递归时压栈 自下至上进行合并
如果某棵子树深搜完之后栈内元素数>=b 就把当前的栈内元素合并为一个块
但是这种方法存在一个问題 就是如果某棵子树深搜之后不到b 去深搜下一个子树 可能在下一个子树内部的某个位置超过b
这样会导致分成的块不连通
因此我们在每次进叺递归时维护一个栈底对于当前子树来说这个栈底就是整个栈的底,栈底以下的元素不能修改或弹栈
这样当一棵子树深搜过后由于子树內未分块节点不超过b之前搜过的未分块节点数也不超过b,因此每块不超过2b
那么题目为什么给了3b呢
深搜结束后可能会剩余一些节点,这些节点的数量不超过b而且一定与当前分出的最后一块连通
因此我们将剩余节点分到最后一块中,可以保证最后一块的大小不超过3b