树上启发式合并总结

树上启发式合并 (dsu on tree)

或许应该叫树上并查集呵呵～～

引理：假设一共有n个人，初始时每个人各自成一个集合，期间不断有合并集合的行为发生任意两个集合进行合并时，小集合里的每个人都会喊一次 “hello world”所有人都在一个集合时，过程停止.请问最多能听到多少次 “hello world”
答案：n*log(n)。证明容易想到就不赘述

树上启发式合并过程：
void dfs(u, keep)，u表示当前节点，keep表示是否保留子树u对信息的贡献

1. 先遍历所有轻儿子的子树，遍历结束时，消除对信息的贡献，dfs(轻儿子，0)
2. 再遍历唯一重儿子的子树，遍历结束时，保留对信息的贡献，dfs(重儿子，1)
3. 考察单个节点u，对信息进行贡献
4. 再遍历所有轻儿子的子树，上面的每个节点，都重新对信息进行贡献
5. 得到子树u的答案
6. 如果keep=0，消除子树u的贡献，如果keep=1，保留子树u的贡献

启发在哪：我们每次都选择轻儿子重新遍历

复杂度分析：
乍一看像是n^2但是我们这里巧妙地转换成了引理里面的场景。每个子树重复的仅仅是他的轻儿子
容易知道我们每个节点最多在轻边上重复logn次。这是因为我们是轻节点v，sz[v] < sz[u] /2(这里u是v的父节点)于是每次轻节点重复贡献都会使自己的size加倍于是每个节点最多logn次，而最多有n个轻节点所以复杂度为n*logn

void solve(int u)
{
    for (int v : g[u])
    {
        if (v == fa[u] || v == son[u])
            continue;
        if (v != son[u])
            solve(v);
    }
    if (son[u])
        solve(son[u]);

    for (int v : g[u])
    {
        if (v == fa[u] || v == son[u])
            continue;
        for (int i = dfn[v]; i < dfn[v] + siz[v]; i++)
        {
            add(id[i], 1);
        }
    }
    add(u, 1);
    ans[u] = diff;
    if (fa[u] && son[fa[u]] != u)
    {
        for (int i = dfn[u]; i < dfn[u] + siz[u]; i++)
        {
            int v = id[i];
            add(v, -1);
        }
    }
}

这里仅仅是写了solve，需要根据题目再更改add