复习板子. 树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等. 树剖的思路其实不难, 主要是代码长... 考虑如何把一棵树通过编号处理成尽量少的链, 同时保证每棵子树/每条链的编号都连续. 容易发现dfs序就满足前者, 这样就保证了每棵子树都在一个连续区…

复习下树上常见算法... 本文中都是远古代码, 一切Bug概不负责. lca最暴力的求法就是x,y一次次往上跳, 这样效率显然很低, 考虑优化, 有两种途经: 树上倍增 dfs预处理一个倍增找父亲节点的数组, x,y成倍的往上跳, 时间复杂度降为log级 通常树上倍增的套路都是设$ F[i][j]$为节点$ i$的第$ 2^j$个父亲, 那么有$ …