浅谈树分治

红太狼 2021-03-28 13:38 622阅读 0赞

点分治

概述

通过求树的重心来给无根树找到一个根。

使得分出的子树的结点个数均不大于n/2,使每次点分治删点后联通块大小减少至少一半。

保证递归层数最多logn。

总复杂度O(nlogn)。

不考虑路径修改

【练习题】

【POJ 1741】Tree

【IOI2011】Race

【SPOJ 1825】免费旅行

考虑路径修改

【练习题】

边分治

【练习题】

【SPOJ 1825】免费旅行

【ZJOI2007】Hide捉迷藏

【HNOI2015】开店

【ZJOI2015】幻想乡战略游戏

【WC 2014】紫荆花之恋

发表评论

表情:
评论列表 (有 0 条评论,622人围观)

还没有评论,来说两句吧...

相关阅读

    相关 分治

    点分治 概述 通过求树的重心来给无根树找到一个根。 使得分出的子树的结点个数均不大于n/2,使每次点分治删点后联通块大小减少至少一半。 保证递归层数最多logn。 ...