树上启发式合并

启发式合并

内容

启发式算法为一类根据人类经验智慧实现的优化算法的统称

一组操作既有两棵树的合并，也有对某个节点的查询
如果我们就纯模拟去写，若所有的树都是一个点，我们有可能会合并出一条链
这样在我们每次查询的时候都是 $O(n)$ 的

这里就体现了人类智慧的重要性：
我们每次将较小的子树合并给较大的子树，这样我们的查询的路线长度是不会变的，从而达到查询的优化
这便是启发式合并

具体应用

有并查集的合并，将小的集合合并入大的集合

与按秩合并不同，按秩合并是将深度较小的合并给深度较大的

树上启发式合并

内容

又称 $dsu\;on\;tree$ ，但并不是树上并查集
是一种根据启发式合并扩展出来的思想
首先在启发式合并内有集合大小一说，那么在树上问题中，集合大小就是子树大小
根据子树大小可以划分为轻子树和重子树
这样启发式合并的内容转换过来就是 将轻子树合并入重子树中

实现

如果有一个场景是我们要统计每一个节点子树的信息

我们要利用轻儿子和重儿子，所以首先预处理出来每个点的重儿子

由于是树上问题，所以我们开一个 dfs_main (u, fa) 记录信息
$DFS$ 是链式递归，我们如果回溯统计，那么两个同级节点中，先进行递归的节点对我们记录的信息会对后递归的节点的信息产生影响，而这两者是互不属于子树的
所以我们一次统计一条链，那么就可以只统计重链

对于一个节点，我们只在回溯时只统计其重儿子（即回溯统计每条重链），轻儿子的答案我们在获取之后，将其造成的影响删除
然后对于一个节点在最后暴力统计其所有轻子树，这样在最坏的情况下离线合并完所有的节点的时间复杂度为 $O(nlogn)$

伪代码

dfs ( u, fa, keep ):                    // dfs(当前节点，父节点，是否保留) 记录信息
    for ( v in u.light_son ):           // 先进入轻儿子走每条新重链
        if ( v != fa ):                 
            dfs ( v, u, false )
    if ( u.weight_son ):                // 进入这条重链继续走
        dfs ( u.weight_son, u, true )

    count(u, &sum)                      // 统计出这个点的答案
    res[u] = sum
    if ( !keep ):                       // 不保留，即为轻儿子，说明这条重链回溯到头了
        clear(u, &sum)                  // 清除这个点对记录值的改变

例题

CodeForces600E_LomsatGelral
题目链接 (opens new window)
题解链接 (opens new window)