树上问题维护

乱写的，比较抽象。

重链剖分

基本概念

定义每个点的子树大小为其子树中点的个数，定义一个点的重儿子为其儿子重子树最大的点。

每个点与其重儿子相连后形成若干条重链，我们不难构造一种 dfn 序使得每条重链的 dfn 连续。

性质：每个点的重儿子唯一，每一条树上的链均只涉及 \(O(\log n)\) 条重链。

因为我们构造了 dfn 序连续，于是树链问题转化成修改量级为原问题 \(O(\log n)\) 倍的序列问题。

于是序列上的经典问题基本都能上树，所以我们考虑些特殊情形。

P5314 [Ynoi2011] ODT

给你一棵树，边权为 \(1\)，有点权。
需要支持两个操作：

• 1 x y z：表示把树上 \(x\) 到 \(y\) 这条简单路径的所有点点权都加上 \(z\)。
• 2 x y：表示查询与点 \(x\) 距离小于等于 \(1\) 的所有点里面的第 \(y\) 小点权。

---

\(O(n\log^2n)\) 做法：邻域维护除父亲和重儿子之外的树的数据结构，问题变成 \(n\log n\) 次插入与 \(n\) 次查询第 \(k\) 小。

\(O(\frac {n\log^2 n} {\log \log n})\) 做法：两种做法，可以把前边的问题用 \(k\) 叉树做， 取 \(k=\log \log n\) 即可，也可以将邻域内改成不维护前 \(k\) 大的儿子，取 \(k=\frac {\log n} {\log\log n}\)，这样也是对的。

经过一些乱搞可以做到 \(O(\frac {n\log^2 n} {(\log \log n)^2})\)，有能做到理论下界 \(O(n\log n)\) 的做法但实际效率较低，但它的比较次数是 \(O(n\log n)\) 量级的。

---

换根类问题

我们可以将一类问题概述成：换根，链上/子树 范围修改查询。例如 P3979 遥远的国度。

但是 P3979 实际上还是范围的双半群的查询，简单来说就是换根后查询子树和与树的根和形态并没有关系。

我们可以把换根问题抽象成求一个函数 \(f(r,v)\)，代表求将树的根换为 \(r\) 后子树 \(v\) 经过某种计算后的答案。

虽然这类问题用 TopTree/LCT 可以做为通解，但我们也可以通过一些手段来用树剖做。

我们约定树 \((V,E)\)，将 \(u,v\in V\)，\(u\) 在 \(v\) 子树中记作 \(u\in v\)。

我们记原树的根为 \(rt\)。考虑