动态点分治学习笔记

发现自己根本不会动态点分治,于是来学一学.

在做点分治的时候,把每个重心和它下一层的重心连起来,就形成了一棵新树.

称它为点分树,根据点分治的性质,这棵树的根是原树的重心,且它的树高是 $O(\log n)$ 的.

对于点分树上的每个点,维护它作为重心时管辖的那个连通块的信息.

单点修改某个点的点权时,就在点分树上暴力向上跳,把跳到的点的信息更新一遍,只会修改到 $O(\log n)$ 个点.

于是我们通过在点分树上维护信息,就实现了支持单点修改权值的点分治,这就是动态点分治.

大概可以把点分树维护信息的模式看成线段树维护信息的模式,单点修改时向上不断 pushup 即可.

bzoj 1095 捉迷藏

如果没有修改操作,直接点分治,在分治中心处用不在一棵子树内的深度最大的两个黑色节点更新一下答案.

现在增加了修改颜色的操作,对每个点开两个 multiset .

第一个 multiset 维护它管辖的所有黑点中到它的父亲的所有距离.

第二个 multiset 维护它在点分树中每个儿子的第一个 multiset 中的最大值,用其中最大的两个数更新答案.

若自己是黑点,那么第二个 multiset 里面还要放入一个 $0$ .

还需要开一个 multiset 维护全局的答案.

有修改操作时,就在点分树上暴力跳,并更新跳到的 multiset 以及维护答案的 multiset.

修改时,把原来的贡献删掉,修改之后,再把新的贡献加进去.

时间复杂度 $O(n\log^2 n)$ .

注意点分树的形态与原树不一样,算距离时要在原树上求出 lca 来算.

code

bzoj 3730 震波

考虑建出点分树,每次询问与 $x$ 距离 $\le k$ 的点权和时,就在点分树上跳.

若从重心 $a$ 跳到了重心 $b$ ,那么 $b$ 所管辖的连通块中,去掉 $a$ 的那一部分,剩下的点到 $x$ 的路径都会经过 $b$ .

那么将 $b$ 所管辖的连通块中,与 $b$ 距离 $\le k-dis(x,b)$ 的点权和计入答案.

再减去 $a$ 所管辖的连通块中,与 $b$ 距离 $\le k-dis(x,b)$ 的点权和.

用动态分配内存,给每个点开 $2$ 个树状数组,都以距离为下标,分别维护到自己的,到父亲的点权前缀和.

修改时就在点分树上跳,把 $O(\log n)$ 个祖先的树状数组都改一遍.

时间复杂度 $O(n\log^2 n)$ ,空间复杂度 $O(n\log n)$ .

code

bzoj 4372 烁烁的游戏

这个题和震波几乎是一样的.

用树状数组去维护以深度为下标的点权差分值就可以了.

code

SCOI2018 D1T1 树

有一棵 $n$ 个点的无根树,每个点有点权.

需要支持以下两种操作:

询问: 给出一个点 $u$ ,询问从 $u$ 出发的简单路径中,最大的点权和.

修改:将一个点 $u$ 的点权修改为 $v$ .

操作总次数为 $m$ .

$n,m\le 10^5$ ,时间限制 3s ,空间限制 64MB .

建出点分树,以 $u$ 出发的简单路径可以看成这样的形式.

从 $u$ 出发,先到 $u$ 在点分树上的某个祖先 $w$ (可以是自己),再到 $w$ 管辖的某个点 $v$ .

对每个点开两个 multiset .

第一个 muliset 维护所有它管辖的点到它在点分树上的父亲的路径权值.

第二个 multiset 维护它在点分树上所有儿子的,第一个 multiset 中的最大值.

询问时,在点分树上往上跳,从 $a$ 跳到 $b$ 时,将 $a$ 对 $b$ 的第二个 multiset 的贡献临时去掉,再查询 $b$ 的第二个 multiset 中的最大值,就一定是从不被 $a$ 管辖的点来的,再加上 $b\to u$ 的点权和 (不算 $b$ ) 来更新答案.

修改时,在点分树上往上跳,把影响到的祖先全部修改过来,并在树状数组上更新重链点权前缀和.

需要一些高超的卡空间技巧.

short + char 可以拼出 $\frac 3 4$ 个 int .

code