近几天跟着dreagonm大佬学习了\(dsu\ on\ tree\)，来总结一下：

\(dsu\ on\ tree\)，也就是树上启发式合并，是用来处理一类离线的树上询问问题（比如子树内的颜色种数）的不二法宝。它不仅好想好写，还有着\(O(nlogn)\)的优秀时间复杂度（划重点）。

结合一道例题来讲吧：

CF600E Lomsat gelral

题目大意：

一棵树有\(n(n\leqslant 10^5)\)个结点，每个结点都是一种颜色，每个颜色有一个编号，求树中每个子树的最多的颜色编号的和，对于每个结点都输出答案。

首先我们考虑暴力怎么做：首先\(dfs\)每一个结点，用一个\(cnt\)数组，记录在当前子树中各个颜色出现的次数，遍历子树并更新\(cnt\)数组和答案，最后清空数组。

这样的复杂度是\(O(n^2)\)的，显然过不去。仔细想一下上面暴力的过程，我们会发现其实在清除的时候，最后一棵子树是没必要清的，我们可以把它对\(cnt\)数组的贡献一直传上去。于是我们想到了如果人为地使重儿子是最后一棵子树的话，岂不美哉。于是我们在\(dfs\)时最后访问重儿子就行了，然后复杂度就被优化到\(O(nlogn)\)了。

综上所述，代码大概会长成下面这样(Show me the code)：

void calc(int u, int fa, int k) //k的取值为1和-1,分别对应累加和清除

{

    cnt[color[u]] += k; //把当前结点的颜色累加到cnt中

    if(k > 0 && cnt[color[u]] >= maxcnt) //更新答案

    {

        if(cnt[color[u]] > maxcnt) sum = 0, maxcnt = cnt[color[u]];

        sum += color[u];

    }

    for(int i = 0, v; i < G[u].size(); ++i)

    {

        v = G[u][i];

        if(v == fa || vis[v]) continue; //vis标记表明v已经计算过了

        calc(v, u, k); //递归计算子节点

    }

}

void dfs2(int u, int fa, int keep) //keep为一表明当前结点在重儿子的子树中,需要保留答案

{

    for(int i = 0, v; i < G[u].size(); ++i)

    {

        v = G[u][i];

        if(v == fa || v == hson[u]) continue; //先访问轻儿子

        dfs2(v, u, 0);

    }

    if(hson[u]) dfs2(hson[u], u, 1), vis[hson[u]] = 1; //再访问重儿子,一定要打上vis标记

    calc(u, fa, 1); //累加答案

    ans[u] = sum;

    if(hson[u]) vis[hson[u]] = 0; //一定要清除标记

    if(!keep) calc(u, fa, -1), sum = maxcnt = 0; //清除答案

}

是不是很简单，再来看一道题：

CF570D Tree Requests

题目大意：

给定一个以\(1\)为根的\(n\)个节点的树，每个点上有一个字母(\(a-z\))，每个点的深度定义为该节点到\(1\)号节点路径上的点数.每次询问\(a,b\)查询以\(a\)为根的子树内深度为\(b\)的节点上的字母重新排列之后是否能构成回文串。

很明显是个树上启发式合并。显然，只要深度为\(b\)结点的所有颜色中，至多有一种的数量为奇数就可以构成回文串了。

直接上代码吧：

#include <bits/stdc++.h>

using namespace std;

#define N 500000

#define pb push_back

#define pii pair<int, int>

#define mp make_pair

#define are =

#define son G[u][i]

int idx(char c)

{

    return c-'a';

}

int n, m, w[N+5], cnt[N+5][26], sz[N+5], vis[N+5], d[N+5], hson[N+5], ans[N+5];

vector<int> G[N+5];

vector<pii> Q[N+5];

void dfs1(int u)

{

    sz[u] = 1;

    for(int i = 0, you; i < G[u].size(); ++i)

    {

        you are son;

        d[you] = d[u]+1;

        dfs1(you);

        sz[u] += sz[you];

        if(sz[you] > sz[hson[u]]) hson[u] = you;

    }

}

void calc(int u, int k)

{

    cnt[d[u]][w[u]] += k;

    for(int i = 0, you; i < G[u].size(); ++i)

    {

        you are son;

        if(vis[you]) continue;

        calc(you, k);

    }

}

void dfs2(int u, int keep)

{

    for(int i = 0, v; i < G[u].size(); ++i)

    {

        v = G[u][i];

        if(v == hson[u]) continue;

        dfs2(v, 0);

    }

    if(hson[u]) dfs2(hson[u], 1), vis[hson[u]] = 1;

    calc(u, 1);

    for(int i = 0, id, d, t; i < Q[u].size(); ++i)

    {

        id = Q[u][i].first, d = Q[u][i].second, t = 0;

        for(int j = 0; j < 26; ++j)

            if(cnt[d][j]&1) t++;

        ans[id] = t > 1 ? 0 : 1;

    }

    if(hson[u]) vis[hson[u]] = 0;

    if(!keep) calc(u, -1);

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = 2, fff; i <= n; ++i) scanf("%d", &fff), G[fff].pb(i);

    char ccc;

    for(int i = 1; i <= n; ++i) cin >> ccc, w[i] = idx(ccc);

    d[1] = 1;

    dfs1(1);

    for(int i = 1, x, y; i <= m; ++i) scanf("%d%d", &x, &y), Q[x].pb(mp(i, y));

    dfs2(1, 0);

    for(int i = 1; i <= m; ++i)

    {

        if(ans[i]) printf("Yes\n");

        else printf("No\n");

    }

    return 0;

}