树上问题
记录一下这一类问题。
好题の记载
T0
切水题必备策略：子树问题转为 \(dfs\) 序，链上问题转为树上差分。
同一子树的 \(dfs\) 序是连续的，该子树在序列中的位置为 \([dfn_u,dfn_u+siz_u-1]\) 。
树上差分需要用到求 \(LCA\) ，将 \(u,v\) 之间的路径转为 \(f_u+f_v-f_{LCA}-f_{fa[LCA]}\)，\(f_x\) 表示 \(x\) 到根节点的路径。
T1
P4211 [LNOI2014]LCA
每次给出 \(l,r,x\) , 定义 \(dep_u\) 为 \(u\) 节点到根节点的距离+1，求 $ \sum_{i=l}^r dep[LCA(i,z)]$ 。
\(n\) 个节点 ，\(m\) 次询问 ，其中 \(n,m \leq 5e4\) 。
题目很简洁，我们如果暴力求每一个 \(LCA\) ，复杂度将是 \(O(n^2\log n)\) 的，需要转换式子。考虑到每一个询问有一个点 \(z\) 是固定的，不妨从这里入手 。
因为有一个定点，所以所有枚举到的 \(LCA\) 一定是在 \(z\) 到根节点的这条链上（包括 \(z\) 节点），而且 \(LCA\) 同样在另一个节点到根节点这条链上，取第一个交点就好了。所以求 \(dep[LCA]\) 就变成了求这两条路径的交集就好了。
如图为求 $ \sum_{i=2}^4 dep[LCA(i,5)]$ 时的权值 ，易得答案为节点 \(z\) 到根节点之和为 \(5\)
考虑离线询问为 \(\sum_{i=1}^r dep[LCA(i,z)]- \sum_{i=1}^{l-1} dep[LCA(i,z)]\)，写个树剖套一个线段树就好了，总的复杂度为\(O(n\log^2n)\) 。写代码的时候记得注意取模以及相减的时候避免出现负数。 AC 记录
T2
Lomsat gelral
对于每一个 \(i\in[1,n]\)，求出以 \(i\) 为根的子树中，占数量最多的颜色的编号和。\(n\leq10^5\) 。
考虑线段树合并，递归完成每一个子节点后与根节点合并，维护的将是颜色的权值线段树，复杂度为 \(O(n\log n)\) ，时空都一样。注意 \(\text{pushup}\) 的时候如果碰到数量一样多的颜色要并起来，且计数器要开 long long 。
考虑 \(\text{dsu on tree}\) ，先递归解决轻儿子，然后在计数器中删掉贡献，最后解决重儿子，然后再直接把其他轻儿子合并上去，总的复杂度也是 \(O(n\log n)\) 。
T3
P4556 [Vani有约会]雨天的尾巴
每次给出 \(u,v\) ，在他们最短简单路径上加权值为 \(w\) 的标记，问最后每一个节点的最多权值的数值。
考虑线段树合并，对于每一个操作打上树上差分标记，最后统一 \(dfs\) 一次，暴力 \(\text{merge}\) 所有的信息，时间复杂度 \(O(n\log n)\)。
考虑树链剖分，在线做法，每个操作都用树剖一条链一条链去跳，再用线段树维护，时间复杂度 \(O(n\log^2 n)\)。
考虑 \(\text{dsu on tree}\)，和线段树合并一样先打上差分标记，再遍历轻儿子删贡献，暴力 \(\text{merge}\) 到重儿子上，时间复杂度 \(O(n\log n)\)。