模板及讲解
倍增LCA
倍增思想，维护$deep[i], pre[i][j]$为点$i$的深度和点$i$的$2^j$个祖先结点
然后对于每一对$x, y$求$LCA(x, y)$，先把深的结点提上来和浅结点深度相同，如果此时$x, y$都相同，说明$x, y$在同侧，输出$x, y$任意一个即可，否则再一起提上来直到两点相等，输出$pre[x][0]$或者$pre[y][0]$
跳的时候跳二进制，即
设$del = deep[b] - deep[a] (deep[b] >= deep[a])$
如果 $del = 5$， 二进制为$101$
那么从左往右扫描，第$i$位为$1$的就跳$2^i$个点
$del = 5$时，跳$2^2$和$2^0$即可
DFS 序
DFS序的一大重要性质即为连续的一段是一个子树，很多问题可以转化为此。
DFS 序经典问题
给定一棵带点权树根为$1$。
1、单点修改，子树查询 (直接维护)
直接用数据结构维护 DFS 序即可。
2、树链修改，单点查询 (贡献)
考虑将树链分割。若修改$(u,v)+1$则等价于修改$(1,u)+1, (1,v)+1, (1, LCA)-1, (1, fa(LCA)-1)$
那么只用处理根到某个点的树链修改。
修改即修改$dfn(u)+1, dfn(v)+1, dfn(LCA)-1, dfn(fa(LCA))-1$
考虑一个查询一个点$y$，由贡献来看，只有$y$子树的点会对$(1,y)$产生贡献。所以直接查询$y$子树即可。
3、树链修改，子树查询 (贡献)
考虑将树链分割。若修改$(u,v)+1$则等价于修改$(1,u)+1, (1,v)+1, (1, LCA)-1, (1, fa(LCA)-1)$
那么只用处理根到某个点的树链修改。
修改即修改$dfn(u)+1, dfn(v)+1, dfn(LCA)-1, dfn(fa(LCA))-1$
考虑一个查询一个子树$y$，由贡献来看，只有$y$子树的点会对$(1,y)$产生贡献。
这里和上面不一样了，设$dep(x)$为$x$深度，$v(x)$为数据结构上$x$的权，则$\forall x \in \operatorname{subtree}(y)$，他的贡献为$(dep(x)-dep(y)) \times v(x)$
转化，得$dep(x) \times v(x) - dep(y) \times v(x)$
写成和的形式，则$\sum\limits_{x \in \operatorname{subtree}(y)} dep(x) \times v(x) - dep(y) \times v(x)$
即$\sum\limits_{x \in \operatorname{subtree}(y)} dep(x) \times v(x) - dep(y) \sum\limits_{x \in \operatorname{subtree}(y)} v(x)$
用数据结构维护$dep(x) \times v(x), v(x)$即可求解。
4、单点修改，树链查询 (差分序列)
考虑将树链分割。若查询$(u,v)$则等价于查询$(1,u)+ (1,v)-(1, LCA)-(1, fa(LCA)-1)$
那么只用处理根到某个点的树链查询。
对于修改$y$，维护差分序列，那就直接差分点$y$的子树即可，答案即为$\sum\limits_{i=1}^{dfn(y)} val(i)$。
5、子树修改，单点查询 (贡献+差分序列 / 直接维护)
对于询问$y$，只有修改$x$是$y$的祖先$x$才会贡献$y$。
所以单点修改$x$，查询$(1,y)$的权和，转化为问题 $4$
或直接用数据结构维护 DFS 序即可。
6、子树修改，子树查询 (直接维护)
直接用数据结构维护 DFS 序即可。
7、子树修改，树链查询 (贡献+差分序列)
和 $4$ 类似的问题。这里就是要处理一下深度，用类似 $2$ 的方法处理即可。
例题：Bzoj 4034
总结：
DFS序的问题主要有几种处理方法：
1、直接维护 (维护原数组)
2、贡献法
3、维护差分序列 (询问前缀和)
本质上还是要将询问变为询问子树(维护原数组)，询问前缀和(维护差分序列)
路径交 / 并问题
路径并：Bzoj 3991，Loj 10132(多条路径并)
路径交：CF 832D(两条路径交，并且有一个端点重合)，Hdu 6110(多条路径交)
判两条路径有没有交，只要一条链的$lca$在另一条链上就一定有交；取两条路径的交，把两条路径的端点两两求出四对$lca$，最深那两个就是路径交。
