dsu on tree，树上启发式合并，和dsu并查集没有什么太大关系。是一种用于解决一类树上无修改可离线子树信息统计询问问题的技巧，优点是常数较小，代码复杂度低，实现较快。

思考一下有根子树信息统计类问题，我们想到的最暴力的想法就是dfs，但是当数据范围达到$10^5$量级时，dfs的时间复杂度显然不是那么优秀，这个时候我们发现，当x是y的子节点时，dfs（x）其实是dfs（y）的一个子问题，我们可以让dfs（y）继承dfs（x）的信息然后dp转移。但是有时候要你统计的信息并不是那么容易转移的，比如众数、不小于k的数的个数之类。所以我们只能让dfs（y）继承某个子节点的信息，然后暴力统计其他子节点的信息，将信息合并后再进行清空。那么保留哪个子节点的信息呢？贪心地想，既然都要保留一个子节点的信息，那么我们直接保留子树最大的节点的信息，暴力求其他子节点的信息。这就是dsu on tree。

总结一下dsu on tree的算法步骤：
先进行树链剖分找到重儿子
遍历每一个节点
解决所有的轻儿子同时消除影响
解决重儿子不消除影响
统计轻儿子对答案的影响
更新答案并删除轻儿子对答案的影响

下面我们看两道例题：
CF600E Lomsat gelral

题目链接：http://codeforces.com/problemset/problem/600/E

题意：给你一棵n个点的有根树，以1为根，每个点有一种颜色。我们称一种颜色占领了一个子树当且仅当没有其他颜色在这个子树中出现得比它多。求占领每个子树的所有颜色之和。

参考代码：

#include <iostream>

using namespace std;
struct Edge
{
    int to, next;
} edge[200005];
int head[200005], tot;
int son[100005], siz[100005], fa[100005], L[100005], R[100005], index[100005], col[100005], cnt[100005];
long long ans[100005], sum;
int maxsum, dfn, n, bigson;

void add(int u, int v)
{
    edge[++tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot;
}

void dfs(int now, int father)
{
    siz[now] = 1;
    son[now] = 0;
    fa[now] = father;
    L[now] = ++dfn;
    index[dfn] = now;
    for (int i = head[now]; i; i = edge[i].next)
    {
        if (edge[i].to == father)
            continue;
        dfs(edge[i].to, now);
        if (siz[edge[i].to] > siz[son[now]])
            son[now] = edge[i].to;
        siz[now] += siz[edge[i].to];
    }
    R[now] = dfn;
}

void update(int now, int val)
{
    for (int i = L[now]; i <= R[now]; ++i)
    {
        if (index[i] == bigson)
        {
            i = R[index[i]];
            continue;
        }
        cnt[col[index[i]]] += val;
        if (maxsum < cnt[col[index[i]]])
        {
            maxsum = cnt[col[index[i]]];
            sum = col[index[i]];
        }
        else if (maxsum == cnt[col[index[i]]])
            sum += col[index[i]];
    }
}

void dsu(int now, bool del)
{
    for (int i = head[now]; i; i = edge[i].next)
        if (edge[i].to != fa[now] && edge[i].to != son[now])
            dsu(edge[i].to, true);
    if (son[now])
    {
        dsu(son[now], false);
        bigson = son[now];
    }
    update(now, 1);
    ans[now] = sum;
    if (del)
    {
        bigson = 0;
        update(now, -1);
        maxsum = sum = 0;
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> col[i];
    for (int i = 1, u, v; i < n; ++i)
    {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 1);
    dsu(1, false);
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << " ";
    return 0;
}

CF570D Tree Requests

题目链接：https://codeforces.com/problemset/problem/570/D

题意：给你一棵n个点的有根树，以1为根，每个点有一个字符。对这棵树进行m次询问，每次询问以v为根节点的子树高度为h的子节点能否组成一个回文串。

参考代码：

#include <bits/stdc++.h>
#include <vector>

using namespace std;
struct Edge
{
    int to, next;
} edge[500005];
struct Query
{
    int id, h;
};
int head[500005], tot;
int son[500005], dep[500005], siz[500005], L[500005], R[500005], index[500005];
int a[500005], cnt[500005][26], ans[500005], tmp[500005];
char s[500005];
int n, m, dfn;
vector<Query> query[500005];

void add(int u, int v)
{
    edge[++tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot;
}

void dfs(int now, int depth)
{
    siz[now] = 1;
    son[now] = 0;
    dep[now] = depth;
    L[now] = ++dfn;
    index[dfn] = now;
    for (int i = head[now]; i; i = edge[i].next)
    {
        dfs(edge[i].to, depth + 1);
        if (siz[edge[i].to] > siz[son[now]])
            son[now] = edge[i].to;
        siz[now] += siz[edge[i].to];
    }
    R[now] = dfn;
}

void update_point(int now, int val)
{
    if (cnt[dep[now]][a[now]] % 2 == 0)
        tmp[dep[now]]++;
    else
        tmp[dep[now]]--;
    cnt[dep[now]][a[now]] += val;
}

void update_tree(int now, int val)
{
    for (int i = L[now]; i <= R[now]; ++i)
        update_point(index[i], val);
}

void dsu(int now, bool del)
{
    for (int i = head[now]; i; i = edge[i].next)
        if (edge[i].to != son[now])
            dsu(edge[i].to, true);
    if (son[now])
        dsu(son[now], false);
    for (int i = head[now]; i; i = edge[i].next)
        if (edge[i].to != son[now])
            update_tree(edge[i].to, 1);
    update_point(now, 1);
    for (int i = 0; i < query[now].size(); ++i)
        ans[query[now][i].id] = (tmp[query[now][i].h] == 0 || tmp[query[now][i].h] == 1);
    if (del)
        update_tree(now, -1);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 2, fa; i <= n; ++i)
    {
        cin >> fa;
        add(fa, i);
    }
    cin >> s;
    for (int i = 0; i < n; ++i)
        a[i + 1] = s[i] - 'a';
    for (int i = 1, v, h; i <= m; ++i)
    {
        cin >> v >> h;
        query[v].push_back({i, h});
    }
    dfs(1, 1);
    dsu(1, false);
    for (int i = 1; i <= m; ++i)
    {
        if (ans[i])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}