图论 - DSU On Tree

原理

DSU On Tree 是利用树链剖分中重儿子的概念，处理对于每个子树的询问的离线算法。

用伪代码写出来会是这个样子：

def dfs(u, keep):
    for v in children[u]:
        if v != son[u]:
            dfs(v, False)

    if son[u]:
        dfs(son[u], True)

    add_node_contribute(u)
    for v in children[u]:
        if v != son[u]:
            add_subtree_contribute(v)

    ans[u] = current_ans
    if not keep:
        clear_subtree_contribute(u)

我们可以看到，每一个节点都被 dfs 函数遍历了一次。

其次，每一个节点都被 add_subtree_contribute 与 clear_subtree_contribute 通过它到根节点的每一条轻边都遍历了一次。

根据树链剖分，每个点到根节点的轻边数量是 $O(\log n)$ 的，所以总的复杂度是 $O(nf\log n)$，其中 $f$ 是添加一次贡献的复杂度。

我们可以发现，这个算法与莫队具有很多的相似之处，都是增加贡献的同时维护答案。

但是，清除贡献的时候，并不需要这个贡献是可撤销的，只需要把它可能修改过的节点恢复到初始状态即可：因为 dfs 的顺序保证了我们最后会处理一段连续的重儿子。

CF600E

这个题目就是典型的可以用 DSU On Tree 解决的题目了。

我们考虑增加一个点的贡献， 只需要维持一个对颜色的计数数组，同时维护一个出现次数的最大值。

当增加这个贡献后，如果超过了出现次数的最大值，那么它就是新的最大值，并且这个最大值只出现了一次；否则，如果等于出现次数的最大值，那么我们把最大值的出现次数增加一次。

注意这里比较绕，因为需要维护“出现次数的最大值在计数数组中的出现次数”这样一看看起来很抽象的东西。

理解了这一点后，我们就可以确保，每次添加贡献都是 $O(1)$ 的，所以复杂度就是 $O(n\log n)$。

如上文所说，我们只需要清除贡献时把它可能改动的地方恢复到初始状态即可。

if (!keep) {
    // 出现次数的最大值
    mxcnt = -1;
    // 出现次数的最大值在计数数组中出现的次数
    mxccnt = 0;
    // 这里运用了 dfs 序的性质, 可以用循环遍历整个子树
    for (int i = dfn[u]; i <= dfn[u] + sz[u] - 1; i++) {
        int v = node[i];
        cnt[col[v]] = 0;
    }
}

CF1709E

套路地，我们记录 $d_u$ 为 $1\sim u$ 点权的异或和，那么 $x\sim y$ 的异或和就会是 $d_x\oplus d_y\oplus a_{u}$，其中 $u$ 是 $x,y$ 的最近公共祖先。

我们不妨就枚举 $u$，然后考虑经过 $u$ 的所有路径，这样枚举是不重不漏的。

当 $u\neq x,u\neq y$ 时，$x,y$ 分布在 $u$ 的不同子树中。我们可以枚举一个子树中的 $x$，然后通过某个数据结构查询前面是否出现过 $y$ 满足 $d_x\oplus a_u=d_y$，然后把 $d_x$ 插入到我们维护的数据结构中，作为有可能对后面的 $x'$ 满足条件的 $y'$。

如果不同子树中并不存在这样的一个点对，那么我们进一步考虑路径的一个端点可能是 $u$。在这种情况下，在 $u$ 的所有儿子中，会存在一个节点 $x$ 满足 $d_x=a_u\oplus d_u$。我们只需要在前文提到的数据结构中查询是否存在 $a_u\oplus d_u$ 即可。

显然这个数据结构可以是 set。

如果我们上面查询到任何一组满足条件的 $(x,y)$，我们肯定需要修改某个节点。

贪心地想，我们只需要把 $a_u$ 该为一个 $2^{N}$，$N$ 足够大，即可保证经过 $u$ 的所有路径的异或和都不为零。

我们至少也需要一次操作才能把经过 $u$ 的所有路径的异或和都变成非零的，而根据上面的方案，修改一次就可以保证，所以最小的修改次数就是 $1$。

我们把 $u$ 修改后，打一个标签，标志它的所有子节点的 $d_u$ 都存在一个 $2^N$，所以后续进行贡献添加的时候就不再需要考虑 $u$ 的子树中的所有节点了。

这样做的复杂度就是 $O(n\log^2n)$，其中有一个 $\log$ 可以用 uset 去掉，但是由于众所周知的原因，CF 的出题人对 uset，umap 不太友好。

CF741D

据说是这个题目的作者提出了 DSU On Tree。

经过排序能成为回文，这个说法等价于至多只有一个数字出现了奇数次，别的都是偶数次。

我们把边权化为点权：把一个连接父亲和儿子的边的边权放到儿子的点上。

我们假设向量 $m_u$ 代表 $u$ 这个点上每一个字母的出现次数，显然他是一个长度为 $22$ 的 $0/1$ 向量。

进一步地，将 $m_u$ 改为到根的所有字母出现的数量，它是一个长度为 $22$ 的向量。

那么，设 $u$ 是 $x,y$ 的最近公共祖先，那么 $x\sim y$ 路径上每个字母出现次数的向量就是 $m_x+m_y-2m_u$。

我们只关心每一个数 $\bmod 2$ 之后的值，所以这个向量的加法实际上可以用异或表示，即 $m_x\oplus m_y\oplus m_u\oplus m_u=m_x\oplus m_y$。

所以我们只需要对每一个点 $u$ 统计经过它的路径有多少对 $x,y$ 满足 $\operatorname{popcount}(m_x\oplus m_y)\le 1$ 即可。

这样，$m_x\oplus m_y$ 的取值只有 $0,2^0,2^1,\dots,2^{21}$ 这 $z=23$ 中可能性。

最后，把经过 $u$ 的答案对子树取一个 $\max$ 就是在 $u$ 的子树中的答案。

复杂度是 $O(nz\log n)$。

ICPC成都 2025 L

由于 $b_u$ 是固定的，所以我们先开一个桶 $c_x$ 记录下来每个 $b_u$ 的出现次数。特别地，对于 $0$ 单独统计。

我们假设目前记录下来了所有的 $b_u$，接下来针对每一个 $a_u$，我们进行如下处理：

1. 如果 $a_u\neq 0$，那么检查 $c_{a_u}$ 是否为正。如果是正的，那么将 $a_u$ 安排到任意一个 $b_v=a_u$ 的位置即可，并且 $c_{a_u}\gets c_{a_u}-1$；如果是非正的，那么我们记录下来这样的失配数量，并且仍然给 $c_{a_u}\gets c_{a_u}-1$。
2. 如果 $a_u=0$，我们只需要最后给它们匹配到没有被匹配的 $b_v$ 即可。

我们发现，这个失配数量实际上就等于 $c_x$ 中所有负数的绝对值加起来。

我们只需要检查这个失配数量，是否能够被 $b$ 中出现的 $0$ 配上即可。

下面是一个可能的实现，其中 add 是添加某个 $b_u$，del 是删除某个 $a_u$。

复杂度是 $O(n\log n)$。

auto add = [&](int x) {
    if (x == 0) return;
    if (cnt[x] < 0) failed--;
    cnt[x]++;
};

auto del = [&](int x) {
    if (x == 0) return;
    cnt[x]--;
    if (cnt[x] < 0) failed++;
};