【学习笔记】DSU on Tree-526互联

概述

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

算法流程

递归处理轻儿子的答案
递归处理重儿子的答案
重新遍历轻儿子子树，计算当前子树的答案
如果当前节点是轻儿子，重新遍历整棵子树，清除答案

发现一个节点被再次遍历当且仅当其所在的子树根为轻儿子，在这之后其所在子树大小至少扩大 \(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);
}