树分块学习笔记
思想
树分块是一种能解决部分操作树上一条链的一种算法。
回忆下序列上的分块，其最精髓的地方在于将序列分成许多段，如果操作的区间包括了某一段，则直接使用整体处理这一段。我们也要使用某种方法使得操作的链也被分成许多块，但像 dfs 序等并不一定能保证整段的大小稳定。
先设定一个阈值 \(S\)，我们要求每一段链的长度接近 \(S\)。一种方法是随机选取 \(\frac n S\) 个点，期望每一段的长度是 \(S\)，但是太过玄学，便不使用这种方法。我们先处理出每个节点的深度及其祖先，若当前没有遍历的最深节点的 \(1\sim S\) 级祖先都没有被选取，则将其 \(S\) 级祖先选取。因为深度从大到小遍历，所以每个选取的点至少会覆盖 \(S\) 个节点，所以至多会有 \(\frac n S\) 个节点被选取，称这些被选取的点为关键点。而相邻两个关键点（需满足这两个点的 \(LCA\) 为其中一个点）间的链便相当于序列上分块的整段。
接下来处理出关键点间两两的答案（两点间仍需满足这两个点的 \(LCA\) 为其中一个点），为了防止查询时时间复杂度过大。预处理的时间复杂度为 \(O(\frac {n^2}{S^2}W)\)，其中 \(W\) 为合并两段区间答案的复杂度。
剩下按照分块的套路，同时将整块答案与散块答案相加即可。具体而言，就是先找到 \(u,v\) 的 \(LCA\)，分别处理 \(u\sim LCA,v\sim LCA\) 即可。（有的题目中需要注意 \(LCA\) 不能被算两次）
实战
P6177 Count on a tree II/【模板】树分块
用 bitset 来表示有哪些颜色出现过，合并的时间复杂度为 \(O(\frac n \omega)\)。