树上启发式合并
树上启发式合并（Dsu on tree），是一个解决树上离线问题的有力算法，一般的复杂度是 \(\mathcal O(n\log n)\)（假定转移可以 \(\mathcal O(1)\) 解决），时间复杂度相比树上莫队等算法还是很优秀的。
算法流程
离线处理，树上 dfs，在遍历每个节点时算出每个点的答案。
我们可以分两步来处理，第一遍 dfs 先预处理出每个点的所需信息，求出每个点的子树的大小和重儿子（所有儿子中子树节点最多的那个儿子）。
第二遍 dfs 计算答案，先遍历所有的轻儿子，计算答案，遍历后将其对结果的影响清空。之后遍历重儿子，不清空影响。最后再遍历所有轻儿子及该节点本身，合并贡献，得出当前节点的贡献。总的复杂度是 \(\mathcal O(n\log n)\) 的。
复杂度证明
任意节点被遍历到的次数是它到根节点的轻边数 \(+1\)，而任意节点到根节点的轻边数都 \(\le \log n\) 的（因为每次合并树的大小至少扩大二倍），所以总的复杂度是 \(\mathcal O(n\log n)\) 的。
例题
- CF600E Lomsat gelral
- CF570D Tree Requests
- CF208E Blood Cousins
- CF246E Blood Cousins Return
- CF1009F Dominant Indices
- CF375D Tree and Queries
- CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
- P4149 [IOI2011]Race