[[点分治]]

LCA

来自异象石的小 Trick
对于一个点列 $a_i$ ，将其按照 $dfs$ 序排序得到 $b_i$
那么有 $dep_{Lca(b_l,b_{l+1}…b_r)}=\min_{i=l+1}^{r} dep_{Lca(b_i,b_{i-1})}$

一个点与另外一个点的 LCA 一定位于其祖先节点中，所以在 “找点对的LCA” 的问题中可以固定一个点，查看这个点的所有祖先的贡献 [[ 测试讲评&习题（二）.pdf | HDU6031，练习题第二题 ]]

Trick

如何判断是否为 一棵树，同时满足无环(LCT/并查集)与点数-边数=1

给出一个树上的点集，问该集合中所有点中的最优点，且所有点只会 整体 向上跳时，若任意一点作为根的子树中的点一定不优时，则可以将这部分点剔除出，剩余点跳跃是均摊 $O(n)$ 的 # P6779 rla1rmdq

对于树上多条路径，找其中两条使得其的交…的问题，可以考虑树链剖分，在每条链上考虑经过这条链的路径在这段上的贡献 # Iron Man