link
相信大家都会 \(\text{Top cluster}\) 分解吧，其实任何的树分块都可以通过随机撒点解决，如果强行需要形成簇的话还需要建一棵虚树。
随机 \(\sqrt n\) 个点，那么就有结论，树上任意一个非标记点到标记点的距离期望 \(\sqrt n\)。
然后我们就可以类似剖分后分块，直接暴力找点完成树上路径问题，树分块的极大优势在于空间小，一般可以类似分块做空间换时间的操作。
对于还需要求 \(\text{LCA}\) 的操作，我们只需要将 \(\sqrt n\) 个点建成虚树，就可以通过分类讨论得到 \(\text{LCA}\)。
P6177
模板，求树上路径本质不同的数的个数。
考虑随机撒点，用 bitset 处理有祖先关系相邻的两个关键点，然后就可以处理出任意有祖先关系的两点之间的答案，由于不同点对最多有 \(n\) 个，复杂度 \(O(\frac{n^2}{w})\)。
对于每次询问，按 \(\text{LCA}\) 分为左右两部分后对两半路径查询答案即可，每次只需要跳关键点，查询中间的答案，再合并答案，复杂度 \(O(\frac{n^2 + nm}{w})\)。
\(\text{Submission}\)
P8353
一棵树，支持路径加，路径查和。
\(1 \le n \le 7\times 10^6,1\le m \le 5\times 10^4\)，时限 5s,空间 64MB
常规树剖肯定不行，我们考虑精细实现树分块。
树分块采用随机撒 \(\sqrt n\) 个点，那么有结论任意两点之间的距离期望是 \(\sqrt n\) 的。
因为要实现求 \(\text{LCA}\)，我们将关键点建成虚树，称虚树外的点为“非树点”。
对于求 \(\text{LCA}\)，我们只需要跳完所有的“非树点”，如果此时两点相遇了，那么 \(\text{LCA}\) 肯定也是“非树点”，暴力跳找到即可。反之，我们就走完了“非树点”，如果此时两点不存在祖先关系，那么我们只需要再走到两点祖先第一个标记点，然后跳标记点第一次相遇就是 \(\text{LCA}\)。
然后我们需要特判两点有祖先关系的情况，这里要处理的问题是向上走的话可能会导致误判，所以我们考虑找到这两个点下面的第一个关键点，由于我们刚才走完了“非树点”，两个点对应的关键点就一定存在。假设我们能找到他们，那么只需要从这两个关键点开始跳，如果有一个关键点没动，说明它是祖先，则其对应的点是 \(\text{LCA}\)。
链修改和链查询是相似的，我们只需要先差分成四个询问，然后解决从某个点到根的问题，还是只需要先走完“非树点”，然后找到第一个关键点再跳关键点即可。在找到第一个关键点的时候，我们也需要找到下面第一个关键点用于更新块总和。
对于如何找到某个点下第一个关键点，我们考虑在预处理每个关键点的第一个关键点父亲的时候，更新其父亲这个子树方向上的第一个关键点为当前点，具体处理可以用一个 umap 记两维信息。
还有一点细节，对于每个关键点不需要及他的编号，每次需要用的时候现求就行，对于每一段链开头和结尾需要特判一下是否为关键点，求某个点的深度的时候也不需要记，可以每次用 \(O(\sqrt n)\) 的时间暴力跳关键点的得到。
每个和块相关的数组只需要开关键点个，所以只需要两个长 \(n\) 的数组，其他就是一些常量了，大概是 \(\text{58MB}\) 左右，跑的也挺快的。
\(\text{Submission}\)