树上启发式合并（dsu on tree）
简单介绍
对于一些在树上统计信息，且对每个节点都有访问其整棵子树的题目，我们可以使用树上启发式合并来简化
启发式合并是一种优雅的暴力，暴力在于他的统计答案是暴力的，而优雅就优雅在他有一个优秀且严格的复杂度
核心思路为：在重链剖分的基础上，对于每个节点，求解完所有轻儿子后再求解重儿子，并将重儿子的答案合并进当前节点中，所以当前节点只需再求解轻儿子即可。
简单伪代码即为：
dfs(x) {for(edge[x]) {int y = to[x];if(y != son[x]) {dfs(y);clear(y);}}dfs(son[x]);// no clear!!cal(x); // get answer in brute force
}
而对于复杂度，提供一个感性证明：
对于每个点 \(x\)，被计算答案（进入dfs函数）的次数应为 (根到 \(x\) 的路径上轻边的数量+1)，
而根据轻重边的性质，从根到任意点的路径上，轻边个数不超过 \(\log n\)，
所以复杂度为 \(O(n\log n)\)。
具体实现
以例题 CF600E Lomsat gelral 为例：
题意：一棵有根树，每个点有颜色，若以 \(x\) 为根的子树内颜色 \(c\) 出现的次数最多，则称为主导色（可有多个），计算每个节点为根的子树的主导色编号和。
在暴力解法中，我们可以遍历每一棵子树，在 \(O(n^2)\) 的复杂度内轻易解决这个问题，而使用树上启发式合并后，可以在 \(O(n\log n)\) 的时间内求解
具体实现与伪代码逻辑相同，不再做过多介绍：
// son[x] -> 重儿子
void dfs1(ll x, ll pre) { // initll maxx = 0; siz[x] = 1;for(ll i = hd[x]; i; i = nxt[i]) {ll y = ver[i];if(y == pre) continue;dfs1(y, x);if(maxx < siz[y]) maxx = siz[y], son[x] = y;siz[x] += siz[y];}
}
void dfs3(ll x, ll pre, ll d) { // brute forcecnt[c[x]]++;if(cnt[c[x]] > maxn) maxn = cnt[c[x]], sum = c[x];else if(cnt[c[x]] == maxn) sum += c[x];for(ll i = hd[x]; i; i = nxt[i]) {ll y = ver[i];if(y == pre || y == d) continue;dfs3(y, x, d);}
}
void dfs4(ll x, ll pre) { // clearcnt[c[x]]--;for(ll i = hd[x]; i; i = nxt[i]) {ll y = ver[i];if(y == pre) continue;dfs4(y, x);}
}
void dfs2(ll x, ll pre) { // mainfor(ll i = hd[x]; i; i = nxt[i]) {ll y = ver[i];if(y == pre || y == son[x]) continue;dfs2(y, x);dfs4(y, x);sum = maxn = 0;}if(son[x]) dfs2(son[x], x);dfs3(x, pre, son[x]);ans[x] = sum;
}
在使用该算法是一定要明确好操作顺序后再开始敲代码，尤其是各个dfs函数的顺序和对 \(sum\)，\(maxn\) 等变量清空的时机等
应用
暂时按照该题单一道一道做，做完在下面补解法