静态链分治 (DSU on Tree) 和树上启发式合并 (Heuristic Merge on Tree) 是简洁有力的处理树上问题的工具，而代价仅为将复杂度乘上 $O(\log n)$。在处理询问时，要求询问离线。
很多人把静态链分治和树上启发式合并混为一谈，但它们其实是截然不同的算法。大家常见并称之为“树上启发式合并”的算法其实是静态链分治。
静态链分治
给定一棵有根树，每个节点上都有一种颜色。回答所有子树中不同颜色的个数。
这是一道老生常谈的经典题，可以用线段树合并 (复杂度 $O(n\log n)$) 和树分块 (复杂度 $O(n\sqrt n)$，又称树上莫队) 等方法解决。但静态链分治也可以解决此题，而且常数较小 (不过我自己写的静态链分治比线段树合并慢)。
利用一个数组 $\text{cnt}$ 来记录每种颜色的出现次数。对树进行重链剖分，处理节点 $i$ 时：
- 先处理所有轻儿子，得到轻儿子子树中所有节点的答案，并在处理完每个轻儿子后清空 $\text{cnt}$。
- 然后处理重儿子，得到重儿子子树中所有节点的答案。处理完后不清空 $\text{cnt}$。
- 最后再遍历轻儿子。至此 $i$ 子树中的所有节点都计入了 $\text{cnt}$，我们得到了 $i$ 的答案。
复杂度证明
静态链分治中有四个产生复杂度的过程：处理轻儿子、清空轻儿子、处理重儿子、遍历轻儿子 (和本身)。
其中，清空轻儿子和遍历轻儿子的复杂度显然都是 $O(n\log n)$，因为每个点到根经过的轻边数都是 $O(\log n)$ 级的。
剩下的过程的复杂度为 $O(n)$。因此总复杂度为 $O(n\log n)$。
例题
树上启发式合并
给定一棵有根树，定义 $d(u,v)$ 为从 $u$ 到 $v$ 的简单路径包含的边数。令 $a=\operatorname{LCA}(u,v),f(u,v)=\gcd(d(u, a), d(a, v))$，求满足 $f(u,v)=i$ 的数对 $(u,v)$ 个数。
这是一道 UOJ 上的题 树上 GCD ，标算为 $O(n\sqrt n)$ 的点分治。但此题也可以用树上启发式合并做到几乎同样的复杂度，并且常数奇小，代码健康。
我们只要求出满足 $d\mid f(u,v)$ 的 $(u,v)$ 个数，就可以通过容斥或者莫比乌斯反演得到答案。我们设定一个分治界限 $B$，对于 $d\in[1,B]$，用动态规划求出满足 $i\mid f(u,v)$ 的点对数，复杂度为 $O(nB)$。
对于 $d\in [B+1,n]$，使用树上启发式合并。设 $dp_{i,j}$ 表示以 $i$ 节点为链顶，且长度为 $j$ 的链的个数。每次将 $i$ 的一个儿子的答案与 $i$ 的答案合并时，我们正常地启发式合并即可。
dp[i].push_back(1);
/* (i,fa[i]) 也是一个长度为 1 的链。
* 这里 dp 数组是倒着的，dp[i][dp.size()-j] 表示长度为 j 的链的个数
*/
if(dp[fa[i]].size() < dp[i].size())
std::swap(dp[fa[i]], dp[i]);
/* 在 C++11 以下的标准中，
* std::swap 不是 O(1) 的，必须使用 dp[fa[i]].swap(dp[i]) 来保证复杂度
*/
for(int j = 0; j < (int)dp[i].size(); ++j)
dp[fa[i]][dp[fa[i]].size() - j] += dp[i][dp[i].size() - j];
这一部分的复杂度为 $O(n\log n)$。
除了合并儿子与父亲的 $dp$ 数组，我们还要统计对答案的贡献：
dp[i].push_back(1);
if(dp[fa[i]].size() < dp[i].size())
std::swap(dp[fa[i]], dp[i]);
int sz1 = dp[i].size(), sz2 = dp[fa[i]].size();
for(int d = B + 1; d <= sz1; ++d){
long long int cnt1 = 0ll, cnt2 = 0ll;
for(int j = d; j <= sz1; j += d)
cnt1 += dp[i][sz1 - j];
for(int j = d; j <= sz2; j += d)
cnt2 += dp[fa[i]][sz2 - j];
ans[d] += cnt1 * cnt2;
// ans[d] 表示满足 d | f(u,v) 的 (u,v) 的个数
}
for(int j = 0; j < sz1; ++j)
dp[fa[i]][sz2 - j] += dp[i][sz1 - j];
这一部分的复杂度较难分析。只有大于 $B$ 的 $\text{sz1}$ 才会对时间产生 $O(\text{sz2}\log\text{sz1})=O(n\log\text{sz1})$ 的贡献，而这种两个 $\text{dp}$ 数组的大小都大于 $B$ 的合并至多出现 $\dfrac{n}{B}$ 次，故复杂度为 $O\left(\dfrac{n^2\log n}{B}\right)$。
取一个 $\sqrt{n\log n}$ 量级的 $B$ 即可得到理论最优复杂度 $O(n\sqrt{n\log n})$。实际上取 $B=10$ 最快。我怀疑这个取值是假的，但构造了许多组数据也没能卡掉。
从这道题我们可以看出来，树上启发式合并本质上就是用启发式合并来优化树形 DP，是一种常数非常小的优秀算法，非常适合代替有根树上的点分治。它的缺陷就是启发式合并只能优化转移方程很简单的树形 DP，不如线段树合并用处广泛。
说到有根树点分治，不能不让人想起购票。不过购票的所谓“分治”其实是 CDQ 分治，要求计算的并非树上路径，因而没法用树上启发式合并了。