这篇文章上次修改于 279 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(13):树上启发式合并

启发式算法是根据经验和直观感觉，对算法的优化，也就是指优化容易理解。

树上启发式合并看似高级，实际上是针对树上不带修改的离线子树问题的解决。

离线指的就是树一旦给出，便不会修改。

例题：树上数颜色

给一棵根为1的树以及每个节点的颜色，每次询问子树颜色种类数。

DFS暴力解决

当然，对于一个树的每个子树或者是节点的所有信息进行保存，可以直接为每个节点保存它的信息，dfs可以很顺利的保存所有的信息并往上传递。显然DFS也可以解决问题，但这句话是不考虑成本的。

通常，子树信息非常庞大，关联性也很复杂，对于两个子树之间的信息合并，也要花费很大的运算成本。

对于树上数颜色问题，内存实际上就有很大的使用，我们需要为每个节点创建一个cnt数组，记录每个颜色的出现次数。节点一旦多，颜色种类一旦很多，那么内存就完全不够使用了。

树上合并

我们储存了每个节点的数据，但实际上并用不到这么多。例如我们先获取所有的查询，那么我们只需要保存对于查询的每个答案。此时，许多数据就不会再使用了，因为题目是离线的，得到答案之后就不需要了。

此时我们就可以考虑只使用一份数据，这份数据随着我们的遍历不断修改，到了对应的节点就会是对应的答案。如果这个点就是我们要查询的点，直接把答案保存，然后继续修改这唯一的一份数据。

那我们现在考虑如何遍历的问题，先考虑对于一个二叉树，它有左子树和右子树，当我从下往上统计完左子树的数据之后，我要是再想统计右子树的数据，那么我的这一份数据就需要清空，因为它们是相互独立的。

清空之后，遍历完右子树，我们就需要把数据传给父节点，此时我们没有左子树的数据（之前被清空了），就需要再去把左子树的数据再统计一遍，这个过程中，一直是右子树的数据加上左子树的数据。走完这个过程，再把这个数据给父节点。

现在如果是三叉树ABC，我们就要走ABCAB，除了最后一个子树，前面的子树我都要再统计一遍。

启发式树上合并

四叉树N叉树？都是一个子树只走一遍，其它所有子树都走两遍。那我们这里就可以优化一下子了。我们选择把最大的子树只走一遍，其它都走两遍，也就是先走所有轻子节点，最后走重，再回头把所有轻节点都统计一遍。

非常容易理解的优化：只能少走一颗子树，选择少走一遍重子树（节点最多的子树）。

code:

struct Detail{
    // 放入需要统计的数据
};

class DSUonTree{
public:
    DSUonTree(int nodeNum,vector<int> * adj_): size(nodeNum + 1), heavySon(nodeNum + 1), treeLeftOrd(nodeNum + 1),
                            treeRightOrd(nodeNum + 1), ord2Node(nodeNum + 1), adj(adj_){
        initDfs(1, 0);
        dfs1(1, 0, false);
    }

    void initDfs(int cur, int parent){
        treeLeftOrd[cur] = ++curDfsOrder;
        ord2Node[curDfsOrder] = cur;

        size[cur] = 1;
        for (int son : adj[cur]){
            if (son == parent) continue;
            
            initDfs(son, cur);
            size[cur] += size[son];

            if (heavySon[cur] == 0 or size[heavySon[cur]] < size[son])
                heavySon[cur] = son;
        }
        treeRightOrd[cur] = curDfsOrder;
    }

    void dfs1(int cur, int parent, bool keep)
    {
        // 计算轻儿子的答案
        for (int son : adj[cur]){
            if (son == parent or son == heavySon[cur]) continue;
            
            dfs1(son, cur, false);
        }

        // 计算重儿子答案并保留计算过程中的数据（用于继承）
        if (heavySon[cur])
            dfs1(heavySon[cur], cur, true);
        

        for (int son : adj[cur]){
            if(son == parent or son == heavySon[cur]) continue;

            for (int ord = treeLeftOrd[son]; ord <= treeRightOrd[son]; ord++)
                addNodeDetail(ord2Node[ord]);
        }

        addNodeDetail(cur);
        
        collectAns(cur);

        if (not keep)
        {
            for (int ord = treeLeftOrd[cur]; ord <= treeRightOrd[cur]; ord++)
            {
                delNodeDetail(ord2Node[ord]);
            }
        }
    }

    void addNodeDetail(int node){
        // 数据结合自行完成
    }

    void delNodeDetail(int node){
        // 数据移除自行完成
    }

    void collectAns(int node){
				// 答案收集自行完成
    }

private:
    vector<int> size, heavySon, treeLeftOrd, treeRightOrd, ord2Node;
    Detail data;
    vector<int> * adj;
    int curDfsOrder = 0;
};

这是一个启发式合并的运算思想代码体现，借助这个模板，需要自行完成数据结合数据移除，答案收集等方面。

模板归模板，重于体现思维。作为另一个例子，体现一种DSUonTree的思想变式

例题：XOR Tree

你有一棵无根树，点数为 𝑛n，每个点有个点权 𝑎𝑢，定义一条路径 𝑃(𝑢,𝑣) 的权值为经过的所有点的点权的异或和。定义一棵树是合法的，当且仅当树上所有简单路径（只经过每个点一次的路径）的的权值都不为 0。

你可以对权值进行修改，可以改成任意正整数，问最少修改多少次才能让这棵树合法。

输出最小修改次数。

强调启发式合并只是一种运算时的工具，题目难点和突破口仍然需要自己去解决，此题应当把异或和作为关键突破口。设xorVal[node] 为从根到 node 的异或和，至于简单路径的异或和，也就是两个点AB作为两段，权值为 xorVal[A] ^ xorVal[B] ^ value[LCA] = 0。

如果对于一颗子树来说，经过子树根节点的所有路径都会与它们俩的LCA也就是根节点有关。所以只要修改根节点的值就会让所有路过这个点的路径权值都不为0.

结合启发式合并

启发式合并的重点在于少走一次最多点的子树。

本题只要考虑不同的点作为这个子树的根，都没有权值为0的路径即可，一旦有0的路径，就去改这个根。

那么作为从下往上的记录，我们就需要记录它们所有子树上的节点的xorVal，当我走到点x，只要记录的点中满足xorVal[A] ^ xorVal[B] ^ value[LCA] = 0，就要修改一次，此时，记录的所有值都可以被清空。用set记录，只需要看 xorVal[p] ^ value[LCA] 是否在 set中即可。

不同点

作为启发式合并的使用，应当关注到这题的不同之处。

我们首先走完所有轻子节点，运算结束之后，再走重子节点，回头我们会再来看一次轻节点。

但是如果在第一次轻子节点中，我们就做了一次值修改，那么从那个被修改的点往下，就都不需要被考虑了，所以在第二遍中，并不用加入所有的点。

应当使用标记，一旦走到标记，就不再往下计算了。而我们这里的启发式合并，是根据记录的元素量来判断哪一个来少走一次。

Mai Icy