无根树分治一般常见于树上路径问题(计数,最优化等).
常见题目如
无权树树上距离为k(对1到n-1求)的路径数量.
点分黑白且可以改,求两端都是黑点的最远路径.
以我的理解,三种分治都是无法互相平替的,对于每种分治我尝试给出一道只能用这个分治的题目.
三种分治复杂度均为 logn*T(n).
其中T(n)为处理一次规模为n的子问题的开销,且需满足T(x)+T(y)<=T(x+y).
点分治
每次取重心,考虑重心所有儿子之间的贡献,去掉重心后再分治连通块.
复杂度证明
重心最大的儿子大小不超过一半,由此可证.
若超过一半重心可向较重那侧偏移,一定更优.
可点修(允许虚点虚边可边修),不需要虚点虚边,信息会被分成多个部分.
边分治
先三度化(多余三个儿子的拆虚点虚边.常见实现如左儿子右兄弟.)
每次取两侧较大那侧最小的边,考虑两侧的贡献,去掉后分治连通块.
复杂度证明
考虑三度化后的重心,该点到其重儿子的连边.
显然重儿子那侧不会小于1/3且不会大于1/2,由此可证.
可以带修(点修边修均可),需要虚点虚边.
1/3分治
不知道中文名叫啥,1/3是个明显特征,就先这么称呼吧.
如果树的大小只有2的时候直接处理两点即可.
否则,每次取重心,把重心的儿子分成两个集合,考虑两个集合之间的贡献.
然后分治到重心+集合0,重心+集合1两部分.
复杂度证明
复杂度基于一定存在一种选取方式使较小的集合大于等于1/3.
而且可以直接贪心,随意按一个顺序枚举,如果加入这个儿子后大小仍小于等于2/3就加入.
两个儿子的情况由重心性质即得.
三个儿子的话会取最小和次小两个,满足条件.
多于三个儿子可合并最小的两个儿子转换成儿子更少的情况.
这样不可能使原本无解变得有解,也不可能创造大于1/2的儿子.
(不过这种情况下贪心的严格正确性还得细证一下,可以自己思考:)
难以点修(可边修),不需要虚点虚边.
标签：重心,复杂度,分治,儿子,三种,虚点,无根树,虚边 From： https://www.cnblogs.com/QedDust/p/18257329