记录一下这一类问题。
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=1}^r {dep}(lca(i,z))- \sum_{i=1}^{l-1} dep(lca(i,z))\)，写个树剖套一个线段树就好了，总的复杂度为
\(O(n\log^2n)\) 。写代码的时候记得注意取模以及相减的时候避免出现负数。
T2
P5305 [GXOI/GZOI2019]旧词
T1的升级版，求 $ \sum_{i=l}^r dep(lca(i,z))^k \bmod 998244353 $ ，数据范围 \(10^5\) 。
和之前一样的思路，但是要维护的值是要求 k 次方的，所以我们考虑差分，让根节点到每一个点路径上的值之和等于这个值，因此每一个线段树上的点需要带一个 \(dep_u^k-(dep_u-1)^k\) 的权值，再相乘就好了，和之前的做法一致了，由于我们还要快速求 \(10^9\) 次方，还得写一个快速幂。
T3
Lomsat gelral
对于每一个 \(i\in[1,n]\)，求出以 \(i\) 为根的子树中，占数量最多的颜色的编号和。\(n\leq10^5\) 。
考虑线段树合并，递归完成每一个子节点后与根节点合并，维护的将是颜色的权值线段树，复杂度为 \(O(n\log n)\) ，时空都一样。注意 pushup 的时候如果碰到数量一样多的颜色要并起来，且计数器要开 long long 。
考虑 dsu on tree ，先递归解决轻儿子，然后在计数器中删掉贡献，最后解决重儿子，然后再直接把其他轻儿子合并上去，总的复杂度也是 \(O(n\log n)\) 。
T4
P4556 [Vani有约会]雨天的尾巴
每次给出 \(u,v\) ，在他们最短简单路径上加权值为 \(w\) 的标记，问最后每一个节点的最多权值的数值。
考虑线段树合并，对于每一个操作打上树上差分标记，最后统一 dfs 一次，暴力 merge 所有的信息，时间复杂度 \(O(n\log n)\)。
考虑树链剖分，在线做法，每个操作都使用树剖一条链一条链去跳，再用线段树维护，时间复杂度 \(O(n\log^2 n)\)。
考虑 dsu on tree，和线段树合并一样先打上差分标记，再遍历轻儿子删贡献，暴力 merge 到重儿子上，时间复杂度 \(O(n\log n)\)。
T5
P4197 Peaks
给定无向带边权带点权图，\(q\) 组询问，每组询问询问从点 \(v\) 开始只经过边权不大于 \(x\) 的路径所能到达的点中第 \(k\) 大点权，如果无解输出 −1。
因为要求走不超过 x 边权的路径，所以肯定是走最小生成树最优，因此建立 \(\text{Kruskal}\) 重构树维护连通性，再写一个树剖 lca 求能到达的边，最后又因为求第 k 大还要套个 dfs 序的主席树去求解静态第 k 大，总的时间复杂度为 \(O(n\log n)\) 。这个题目缝合了很多算法，属于是码农题了。