DSU

简介

$dsu$，也就是数上启发式合并，大概就是暴力

一般 $dsu$ 用来解决一类树上查询问题，无修改，且只有对子树内的询问

这东西大概的做法是对于一个点，首先递归处理所有轻儿子，结束之后消除产生的贡献

递归重儿子，不消除重儿子的贡献

再次暴力一遍所有轻儿子的贡献

统计该点的答案

这样看起来复杂度是 $O(n^2)$ 的

注意到一个点被计算的次数是头顶上轻边的个数

而轻边的个数是 $O(\log n)$ 的

所以复杂度应该是 $O(n\log n)$

大概就是这样，贴个板子

void add(int u) {
    for (int i = in[u]; i <= out[u]; ++i) {
        int c = col[bl[i]], cnt = ++cnt1[c];
        if (cnt > mx) mx = cnt; ++cnt2[cnt]; sum[cnt] += c;
        cnt2[cnt - 1]--; sum[cnt - 1] -= c; 
    }
}

void del(int u) {
    for (int i = in[u]; i <= out[u]; ++i) {
        int c = col[bl[i]], cnt = --cnt1[c];
        if (--cnt2[cnt + 1] == 0 && cnt + 1 == mx) --mx; sum[cnt + 1] -= c;
        cnt2[cnt]++; sum[cnt] += c;
    }
} 

ll ans[maxn];
void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue ;
        dfs(v, u); del(v); 
    }
    if (son[u]) dfs(son[u], u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        add(v);
    }
    int c = col[u], cnt = ++cnt1[c];
    if (cnt > mx) mx = cnt; ++cnt2[cnt]; sum[cnt] += c;
    cnt2[cnt - 1]--; sum[cnt - 1] -= c;
    ans[u] = sum[mx]; 
}

应用

1. 简要题意：给定一棵有 $n$ 个节点的数，每个点有一个权值 $a_i$，求 $\sum_{i=1}^n\sum_{j=i+1}^na_i\oplus a_j=a_{lca(i,j)}$，其中 $\oplus$ 表示异或

   $n\le 10^5,a_i\le 10^6$

   简要题意：我们考虑对于每一个点 $u$，计算其子树内的贡献，那么对于子树内枚举出的点 $v$，可以得到剩下那个点的另一个点权 $a[w]$ 一定为 $a[u]~xor~a[v]$

   然后对于 $(v~xor~w)$ 这一个贡献，我们可以拆位来计算

   对于每个点 $u$，枚举子树内所有 $lca$ 是 $u$ 的点对中的一个点的做法就是 $DSU$，时间复杂度 $O(n\log^2 n)$

   2020 China Collegiate Programming Contest Changchun Onsite F. Strange Memory