【学习笔记】DSU on Tree

概述

DSU on Tree 即树上启发式合并，重点不在“合并”，而在利用树链剖分的性质对子树问题进行复杂度正确的分治。

算法流程

1. 递归处理轻儿子的答案

2. 递归处理重儿子的答案

3. 重新遍历轻儿子子树，计算当前子树的答案

4. 如果当前节点是轻儿子，重新遍历整棵子树，清除答案

发现一个节点被再次遍历当且仅当其所在的子树根为轻儿子，在这之后其所在子树大小至少扩大 \(2\) 倍，因此每个节点最多被遍历 \(O(\log n)\) 次，那么总遍历次数是 \(O(n\log n)\)，若单个节点计算答案复杂度 \(O(k)\)，总复杂度 \(O(kn\log n)\)。

实现如下：

void dfs1(){
    // 求出重儿子
}
void add(){
    // 加入一个节点的贡献
}
void del(){
    // 删去一个节点的贡献
}
void insert(int u){
    // 加入整棵子树的贡献
    add(u);
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==fa[u]) continue;
        insert(v);
    }
}
void erase(int u){
    // 删去整棵子树的贡献
    del(u);
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==fa[u]) continue;
        erase(v);
    }
}
void dfs2(){
    // 递归处理轻儿子答案
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v);
    }
    // 递归处理重儿子答案
    if(son[u]) dfs2(son[u]);
    // 重新遍历轻儿子子树，计算当前子树的答案
    add(u);
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        insert(v);
    }
    // 如果当前节点是轻儿子，重新遍历整棵子树，清除答案
    if(fa[u]&&son[fa[u]]!=u) erase(u);
}

例题

CodeForces-600E Lomsat gelral *2300

维护当前最多出现次数以及对应元素之和即可。

CodeForces-570D Tree Requests *2200

一个判断方式是最多只有一种字符出现次数为奇数，那么字符权值设计成 \(2^c\)，记录一下每个深度的异或和即可轻松判断。

参考资料

• DSU on Tree 总结 - 粗酥雨