题解 P6778 [Ynoi2009] rpdq

· · 题解

本文主要参考 IOI 2021 中国国家集训队论文《浅谈一类树分块的构建算法及其应用》周欣。

我们可以通过简单的转化将问题变为求 (r-l)\sum\limits_{i=l}^r\operatorname{dep}(i)-2\sum\limits_{i=l}^r\sum\limits_{j=i+1}^r\operatorname{dep}(\operatorname{lca}(i,j))。

显然我们只需要维护后面的部分。

考虑莫队，加入/删除一个元素时产生的贡献是经典题，[LNOI2014]LCA，问题转化为链加链查询和。

我们莫队二次离线，这样我们需要一个支持 O(\sqrt n) 给 a_i 加 1，i 取在根到修改点的所有边的编号；O(1) 查询 \sum a_iw_i 的数据结构，w_i 为边权，i 取根到查询点的所有边的编号的数据结构。

我们使用 \text{top cluster} 进行树分块。

定义：

簇是一个联通子图，至多有两个点和全树其他位置连接。

这两个点称为界点，簇内其他点成为内点。

界点间的路径称为簇路径。

树分块可以被认为是把树划分为 O(\frac nB) 个大小为 O(B) 的不交簇。

将界点看为点，簇看为边，形成的树称为收缩树。

构造方法：

我们只在三种情况下把当前点作为界点，并将边弹出。 - 当前点为根节点； - 当前点的儿子中存在两个及以上含有界点的子树； - 栈中边数量大于 $B$。 问题抽象为给定两个序列 $a$，$b$。将序列划分为若干段使得每个子段 $\sum b$ 不超过 $1$，$\sum a$ 不超过 $B$。 直接贪心地取最长的合法前缀就可以了，正确性证明可以见论文，不在此展开。 回到本题，我们预处理出每个点到它所在簇深度小的界点经过的簇路径的边权和和到它所在簇深度小的界点经过的边权和。 每次修改，把修改点所属簇重新计算每个点到它所在簇深度小的界点经过的边权和，对于其余簇，一定只有簇路径上的边被修改，打标记即可解决，最后在收缩树上做一遍前缀和。 查询时将贡献分为三部分： - 收缩树上的前缀和； - 簇内的前缀和； - 被标记维护的部分，即标记乘“每个点到它所在簇深度小的界点经过的簇路径的边权和”。 直接加起来就可以了。 如果你被卡常，不要惊慌，把 `vector` 换成手写的内存池或者 `basic_string` 都能过。 代码就不放了，如果有需要可以私信我。