树上启发式合并：

（注意此处的树上启发式合并和 dsu on tree 的区别）

点分治的内核是为每一条路径选定一个划分点进行划分，通过快速合并划分点两侧的路径计算答案。

事实上，对于树上路径，有一个“天然的划分点”——路径两端点的 LCA。

将 LCA 作为路径的划分点，那么每条路径一定会被考虑且只考虑一次。

在树上进行 dfs 时，遍历到的每个点的不同儿子的子树的节点之间的 LCA 就是这个点。

而对于遍历到的当前节点，依次遍历儿子的子树时，从一个儿子回溯到当前节点，开始遍历下一个儿子后，对于新遍历的儿子的子树内的信息就可以和已经遍历过的儿子的子树信息进行合并。

用数据结构维护信息，因为只能是当前节点的后代节点信息进行合并，而 dfs 时，可能会遍历过当前节点的非后代节点。所以需要对每个节点单独开一个「数据结构」进行统计。

同时，将后代信息合并到当前节点是不断合并集合状态的过程。因为总状态数对应总节点数，所以合并的。采用启发式合并，合并两个「数据结构」的信息时，将信息少的那个「数据结构」的元素暴力取出插入到另一个「数据结构」中。

总时间复杂度：$O(n\log nT(n))$，其中 $T(n)$ 表示「数据结构」插入的时间复杂度。

void merge(/*x 的数据结构*/, /*儿子 u 子树的数据结构*/) {
    if (/*x 的数据结构.size */ < /*儿子 u 子树的数据结构.size*/)
        swap(/*x 的数据结构*/, /*儿子 u 子树的数据结构*/);

    for (auto u : /*儿子 u 子树的数据结构*/) {
        // 合并 x 的数据结构的信息 和 儿子 u 子树的数据结构 的信息，计算贡献
    }
    for (auto u : /*儿子 u 子树的数据结构*/) {
        // 插入 x 的数据结构
    }

    // 清空 儿子 u 子树的数据结构
}
void dfs(int x, int y) {
    for (auto u : p[x]) {
        if (u == y)
            continue;
        dfs(u, x);
        merge(/*x 的数据结构*/, /*儿子 u 子树的数据结构*/);
    }
    // 计算 x 的贡献
    // 添加 x 的信息
}

dsu on tree：

（注意此处的 dsu on tree 和树上启发式合并的区别）

dsu on tree 和树上启发式合并有的地方会混为一谈。

dsu on tree 维护的方式还是和上述做法相同，本质就是枚举分界点，合并两端路径作为答案路径。和树上启发式合并一样，是将路径在 LCA 处合并。

dsu on tree 的时间复杂度分析是基于轻重链剖分的。

简单来说，dsu on tree 就是在从儿子子树回溯时，保留重儿子的信息，清空轻儿子的信息。同时，使重儿子是最后一个被遍历的。递归完儿子后，重儿子信息保留，轻儿子的信息暴力统计一遍（暴力统计的过程可以另写一个递归，也可以利用子树在 dfn 序上是连续的一段去遍历）。

时间复杂度简单说明：

树上任意节点到根节点的轻边数量不超过 $O(\log n)$ 条。

设根到该节点轻边数量为 $x$ 条，该节点的子树大小为 $y$。显然轻边连接的子节点的子树大小小于父亲子树的一半，则 $y<{\displaystyle \frac{n}{2^x}},\because n>2^x\therefore x<\log n$.

如果一个节点是其父亲的重儿子，则任意节点到根的路径上所有重边连接的父节点在计算答案时必定不会遍历到这个节点，所以一个节点被遍历的次数等于它到根节点路径上的轻边数 $+1$，所以一个节点被遍历到的次数就是 $O(\log n)$ 的。

所以 dsu on tree 遍历所有节点的总时间复杂度就是 $O(n\log n)$ 的。

时间复杂度：$O(n\log nT(n))$，其中 $T(n)$ 表示维护信息的时间复杂度。

void dfs(int x, int y) { // 维护重儿子
    fa[x] = y;
    sz[x] = 1;
    for (auto u : p[x]) {
        if (u == y)
            continue;
        dfs(u, x);
        sz[x] += sz[u];
        if (sz[son[x]] < sz[u])
            son[x] = u;
    }
}

void dfs1(int x) { // 将 x 子树的信息和已有信息合并，计算贡献
    for (auto u : p[x]) {
        if (u == fa[x])
            continue;
        dfs1(u);
    }
}
void dfs2(int x) { // 添加 x 子树的信息
    for (auto u : p[x]) {
        if (u == fa[x])
            continue;
        dfs2(u);
    }
}
void dfs0(int x, bool y) {
    for (auto u : p[x]) { // 优先递归轻儿子
        if (u == fa[x] || u == son[x])
            continue;
        dfs0(u, 0);
    }
    if (son[x]) {
        dfs0(son[x], 1);
    }

    // 暴力遍历轻子树
    for (auto u : p[x]) {
        if (u == fa[x] || u == son[x])
            continue;
        dfs1(u);
        dfs2(u);
    }
    if (y) {
        // 回溯时，若要保留则添加 x 的信息
    }
    if (!y) {
        // 回溯时，若不保留则清空信息
    }
}
dfs(1, 0);
dfs0(1, 1);