UPD 17.3.27：这个技巧实际上局限性也很明显。第一只能支持子树查询，第二不支持修改操作。

概述

写这篇文章的原因是NOIP前刷Codeforces做到一道题，用这种方式，以很低的代码复杂度做到的优秀时间复杂度。
于是我学习了一下CF上这篇文章，翻译过来安利一下，也算作是自己的学习笔记吧。

什么是dsu on tree

dsu on tree用来解决这样一类问题：统计树上一个节点的子树中具有某种特征的节点数。
例如子树中颜色为 x 的个数。
这种方法可以做到O(nlogn)的复杂度。
那么dsu到底是个什么玩意呢？其实它的中文译名就是众所周知的并查集…
有的小朋友就会问了，并查集怎么跑到树上去的呢？
恩……其实说白了就是启发式合并：在做一类维护问题的时候，将size较小的合并到较大的size上，从而达到降低时间复杂度的目的。
不是很懂为什么叫dsu，因为并查集的按秩合并思想？

一个例子

以上面的问题举个例子。
给出一棵树，每个节点有一种颜色。
给出若干次询问形如：树中节点 x 的子树中颜色为c的个数。
下面讨论了几种做法。
代码我直接粘的原文代码。

暴力

int cnt[maxn]; void add(int v, int p, int x){ cnt[ col[v] ] += x; for(auto u: g[v]) if(u != p) add(u, v, x) } void dfs(int v, int p){ add(v, p, 1); //now cnt[c] is the number of vertices in subtree of vertice v that has color c. You can answer the queries easily. add(v, p, -1); for(auto u : g[v]) if(u != p) dfs(u, v); }

在这种做法中，每次统计 x 节点前，暴力将x的子树的贡献加入，统计结束后，再暴力删除贡献，消除影响。
时间复杂度 O(n2)
但是这样有很多无用的删除操作，能不能减少这种操作呢。

平衡树启发式合并

map<int, int> *cnt[maxn]; void dfs(int v, int p){ int mx = -1, bigChild = -1; for(auto u : g[v]) if(u != p){ dfs(u, v); if(sz[u] > mx) mx = sz[u], bigChild = u; } if(bigChild != -1) cnt[v] = cnt[bigChild]; (*cnt[v])[ col[v] ] ++; for(auto u : g[v]) if(u != p && u != bigChild){ for(auto x : *cnt[u]) (*cnt[v])[x.first] += x.second; } //now (*cnt)[c] is the number of vertices in subtree of vertice v that has color c. You can answer the queries easily. }

在这种做法中，每个节点开了一棵平衡树。按照dfs序来统计答案。统计到 x 的时候，保留其最大的孩子，将其他孩子合并到最大的孩子上（启发式合并）。
时间复杂度O(nlog2n)
这样虽然减少了操作次数，但是单次操作次数变为了 O(logn)
（Splay的启发式合并是 O(nlogn) 的？但是因为常数和代码复杂度关系，不是很值得专治数据结构学傻）
有没有更优秀的做法呢。

树链剖分

int cnt[maxn]; bool big[maxn]; void add(int v, int p, int x){ cnt[ col[v] ] += x; for(auto u: g[v]) if(u != p && !big[u]) add(u, v, x) } void dfs(int v, int p, bool keep){ int mx = -1, bigChild = -1; for(auto u : g[v]) if(u != p && sz[u] > mx) mx = sz[u], bigChild = u; for(auto u : g[v]) if(u != p && u != bigChild) dfs(u, v, 0); // run a dfs on small childs and clear them from cnt if(bigChild != -1) dfs(bigChild, v, 1), big[bigChild] = 1; // bigChild marked as big and not cleared from cnt add(v, p, 1); //now cnt[c] is the number of vertices in subtree of vertice v that has color c. You can answer the queries easily. if(bigChild != -1) big[bigChild] = 0; if(keep == 0) add(v, p, -1); }

在这种做法中，我们先进行树链剖分。
dfs的时候，首先dfs节点 x 的轻儿子，暴力消去影响，再dfs节点x的下一个轻儿子，一次类推。
然后dfs节点 x 的重儿子，无需消去影响。
在最后，我们为了统计x，再将 x 轻儿子的贡献加回来。
看起来很暴力，但是实际上它的时间复杂度是O(nlogn)的，跑得飞快。
可以这么考虑：只有dfs到轻边时，才会将轻边的子树中合并到上一级的重链，树链剖分将一棵树分割成了不超过 logn 条重链。
每一个节点最多向上合并 logn 次，单次修改复杂度 O(1) 。
所以整体复杂度是 O(nlogn) 的。

其他做法

类似于这种树上子树的统计问题，还有一些其他的做法。

dfs序莫队

一个子树中的节点在dfs序中是连续的，所以可以通过dfs序，将子树问题转化为序列问题，这样就可以跑莫队了。
时间复杂度 O(qn√)

dfs序主席树

还可以通过dfs序建出主席树，查询就是差分后的单点查询。
时间复杂度 O((n+q)logn)
但是空间复杂度是 O(nlogn) 的