树上启发式合并与树上启发式合并

Aug.21

树上启发式合并用于解决「询问每个节点关于其子树的某些信息」的问题。

标题二者分别指

• 树上启发式合并 (DSU on Tree)：专有名词，做法里需要删除轻子树
• 树上启发式合并 (Small-to-Large)：把各个子树当作集合，按小给大合并两个集合容器

为避免歧义，下文分别以「DSU on Tree」与「Small-to-Large」称呼之。而「树上启发式合并」则表示这类通用思路。

* 启发式：基于人类的经验和直观感觉，优化算法

---

DSU on Tree

Idea

因简单的树形 DP 在空间上不能满足，所以不能存储每个节点的信息，而是要资源复用。

又因为在压缩空间后，需要对每个节点暴力统计子树的信息，在时间上又不能满足，所以 启发式地保留重子树的信息 ，以节约时间。

*DSU：并不存在真正的并查集结构，只是借用了 DSU 以启发式合并解决问题的名号（笑

Algorithm

加入重子树 $\rightarrow$ 加入轻子树 $\rightarrow$ 回答询问 $\rightarrow$ 删除轻子树

std::vector<int> parent(N, -1), siz(N);
[&](this auto&& self, int x) -> void {
    if (parent[x] != -1) {
        adj[x].erase(std::ranges::find(adj[x], parent[x]));
    }
    siz[x] = 1;
    for (auto& y : adj[x]) {  // 涉及交换，必须加引用！
        parent[y] = x;
        self(y);
        siz[x] += siz[y];
        if (siz[y] > siz[adj[x][0]]) {
            std::swap(y, adj[x][0]);
        }
    }
} (0);

auto modify = [&](int x, int delta) {
    // 维护相关信息 
    // delta = 1 表示添加元素 delta = -1 表示删除元素 
};
auto calculate = [&](int x) -> void {
    // 利用相关信息计算答案 
};

[&](this auto&& self, int x, bool keep) -> void {
    // 遍历轻子树 递归求解 随后删除 
    for (auto y : adj[x] | std::views::drop(1)) {
        self(y, false);
    }

    // 遍历重子树 递归求解 加入容器 
    if (adj[x].size()) {
        self(adj[x].front(), true);
    }

    // 遍历轻子树 加入容器 
    modify(x, 1);
    for (auto y : adj[x] | std::views::drop(1)) {
        [&](this auto&& self, int x) -> void {
            modify(x, 1);
            for (auto y : adj[x]) self(y);
        } (y);
    }

    // 计算 answer
    calculate(x);

    // 回溯前删除 
    if (!keep) {
        [&](this auto&& self, int x) -> void {
            modify(x, -1);
            for (auto y : adj[x]) self(y);
        } (x);
    }
} (0, true);

Complexity

假设数组修改为 $\mathcal{O}(1)$，DSU on Tree 的时间复杂度是标准的 $\mathcal{O}(N \log N)$。常数极小，可与二分、树状数组相媲美。

口胡证明：只有轻子树需要重新递归遍历修改，因此节点 $x$ 的修改次数等于它到 root 的路径上轻边的数量，这不超过 $\lfloor \log_2 N \rfloor$ 条。因此复杂度 $\mathcal{O}(N \log N)$。

Small-to-Large

Idea

启发式合并
有 $N$ 个集合，欲按特定顺序将其合并，同时计算跨集合的信息。
做法：始终将较小集合的元素逐个取出，先在大集合中查询 / 计算与该元素的跨集合贡献，再将其插入大集合。

应用在树上，把各个子树当作集合。用小子树查大集合，算出不同子树之间的跨集合贡献。这里可以直接把轻子树合并到重子树的里面，就保证了每次都是小并大。

Algorithm

为每个节点维护一个容器，具体有两种写法：

• 继承重子树的容器 $\to$ 遍历所有轻子树的容器逐个加入 $\rightarrow$ 回答询问
• 不管轻重，直接比较容器大小 $\rightarrow$ 将较小集合的元素逐个加入较大的 $\rightarrow$ 回答询问

显然后者更好写，但前者有利于理解。

代码是直接比较容器大小：

[&](this auto&& self, int x) -> void {
    for (auto y : adj[x]) {
        self(y);

        // 启发 
        if (mp[x].size() < mp[y].size()) {
            std::swap(mp[x], mp[y]);  // O(1) 的喵 
        }
        
        for (auto& [v, val] : mp[y]) {
            // 合并子树 
        }
    }

    // 加入当前节点 x 的贡献 

    // 计算当前节点的答案 
} (0);

Complexity

使用 STL，时间复杂度为 $O(N \log^{2} N)$。

口胡证明：任意一个元素每被移动一次，它所在集合的规模至少翻倍，因此每个元素至多被移动 $O(\log N)$ 次，而 set 等 STL 自带 log，总体时间复杂度为 $O(N \log^{2} N)$，空间复杂度 $O(N)$。

多一个 log 这个事情可以上一个数据结构来解决。使用某些数据结构（如线段树合并），复杂度可能为 $\mathcal{O}(N \log N)$ 或 $O(N \log^{2} N)$，常数较大。

另外需要动态分配内存，空间常数也较大。

Comparison

本质都是保留重子树的贡献，只重新遍历 / 合并轻子树。

• DSU on Tree：加入重子树 $\rightarrow$ 加入轻子树 $\rightarrow$ 回答询问 $\rightarrow$ 删除轻子树，复用全局数组。利用重新 DFS 访问 $\log N$ 次保证复杂度。
• Small-to-Large：继承重子树的容器 $\to$ 遍历所有轻子树的容器逐个加入 $\rightarrow$ 回答询问。利用至多合并 $\log N$ 次保证复杂度。

实际上，DSU on Tree 是省去了 Small-to-Large 里「已计算、但暂时用不到」的那些轻子数的信息，转「存储」为「重算」。

最直白：

	DSU on Tree	Small-to-Large
核心	撤销、重算（需支持删除操作）	存储、合并（保留每个子树历史状态）
数据结构	无 / 树状数组（简单）	STL / 线段树合并、主席树（复杂）
时间	小	大（常数或 $\log$）
空间	小	大
码量	适中，模板较多	STL 小，复杂数据结构大
在线 / 离线	只能离线	在线

Problems

CF375D

https://codeforces.com/contest/375/problem/D

有根树，点有颜色。多次询问 $(u, k)$：在子树 $u$ 中，出现次数 $\geqslant k$ 的颜色有多少种。

维护两个东西：

• cnt[c]：当颜色 $c$ 出现的具体次数。
• sum[f]：当前出现次数 $\ge f$ 的颜色有多少种。

DSU on Tree 的修改非常简单，大致是 cnt[c]++; sum[cnt[c]]++; 和 sum[cnt[c]]--; cnt[c]--;。

Small-to-Large 维护 sum[f] 有些繁琐，但也是可以做的。

CF 炸了所以没有代码。

2025 CCPC Beijing Inv. D

https://codeforces.com/gym/105851/problem/D
https://qoj.ac/contest/1986/problem/10516

两棵有根树 $S$ 和 $T$，点数均为 $N$。求二元组 $(x,y)$ 的数量，满足 $x<y$ 且 $\mathcal{LCA}_{S}(x,y)=\mathcal{LCA}_{T}(x,y) = u$。

对树 $S$ 树上启发式合并。

枚举到 $u$ 的子树，需要合并 $u$ 的两个小子树。假设正在枚举 $x$，什么样的 $y$ 才能满足 $\mathcal{LCA}_S(x,y) = \mathcal{LCA}_T(x,y) = u$？如何快速查询这些 $y$ 的数量？

对树 $S$，点对 $(x, y)$ 满足 $x$ 和 $y$ 属于 $u$ 的不同子树，或者其中一个是 $u$ 本身。而全局数据结构（或另一个子树的数据结构）只包含之前已处理过的子树中的节点 $y$。即天然保证了每个符合条件的 $(x,y)$ 只会被统计一次。

对树 $T$，

• 若 $x = u$：$y$ 可以是 $\operatorname{subtree}_T(u)$ 中除了 $u$ 以外的任意节点。形式化地，

  $$\text{Ans} = \text{Query}(L_T(u), R_T(u)) - \text{Query}(L_{T}(u))$$

• 若 $x \neq u$：设 $v=\operatorname{firstChild}_{T}(u, x)$ 是 $T$ 中 $u$ 的子节点，且是 $x$ 的祖先。则 $y$ 必须在 $\operatorname{subtree}_T(u)$ 内，但不能在 $\operatorname{subtree}_T(v)$ 内（否则 $\mathcal{LCA}_T(x,y)$ 会落入 $v$ 或其子树中）。形式化地，

  $$\text{Ans} = \text{Query}(L_T(u), R_T(u)) - \text{Query}(L_{T}(v), R_{T}(v))$$

指向很明显了，要快速查询树上区间被激活的点，上数据结构。

如果用 DSU on Tree，需要树状数组；如果用 Small-to-Large，需要线段树合并。复杂度都是 $\mathcal{O}(N \log^{2}N)$。

代码是 DSU on Tree（完整代码见 AC）：

auto modify = [&](int x, int delta) {
	bit.add(T.dfn[x], delta);
};

auto query = [&](int x, int u) -> i64 {
	if (!T.is_ancestor(u, x)) return 0;
	i64 cnt = 0;
	T.for_each_subtree(u, [&](int L, int R) { cnt += bit(L, R); });
	if (x != u) {
		int v = T.first_child(u, x);
		T.for_each_subtree(v, [&](int L, int R) { cnt -= bit(L, R); });
	}
	return cnt;
};

[&](this auto&& self, int u, bool keep) -> void {
	for (auto& v : S.adj[u] | std::views::drop(1)) {
		self(v, false);
	}

	if (S.adj[u].size()) {
		self(S.adj[u].front(), true);
	}

	res += query(u, u);
	modify(u, 1);

	for (auto& v : S.adj[u] | std::views::drop(1)) {
		// 这里必须先询问再修改，避免算到同一子树内部的贡献 
		[&](this auto&& self, int x) -> void {
			res += query(x, u);
			for (auto y : S.adj[x]) self(y);
		} (v);
		[&](this auto&& self, int x) -> void {
			modify(x, 1);
			for (auto y : S.adj[x]) self(y);
		} (v);
	}

	if (!keep) {
		[&](this auto&& self, int x) -> void {
			modify(x, -1);
			for (auto y : S.adj[x]) self(y);
		} (u);
	}
} (0, true);

【VP 区域赛前勿点】2025 ICPC Chengdu L

有根树，每个节点有 $A_{i}, B_{i}$。点权中 0 表示通配符，0 与任何数相等。对每个子树 $T_{u}$ 判断：多重集 $S_{A}=\lbrace A_{v} : v \in \text{subtree}(u) \rbrace$ 和 $S_{B}$ 是否相等。

设 $c_{A,x}$ 表示多重集 $S_{A}$ 中 $x$ 的数量，$c_{B,x}$ 类似。通配符比较无敌不可能剩下，可以只考虑 $x \neq 0$，那么 $A_{i}=B_{j}$ 需要占用恰好一个位置，$A_{i}$ 找不到伴也需要占用恰好一个位置，所以总共占用 $\sum_{x \neq 0} \max \lbrace c_{A,x},c_{B,x} \rbrace$ 个位置。条件等价于

$$\sum_{x \neq 0} \max \lbrace c_{A,x},c_{B,x} \rbrace \leqslant |T_{u}|$$

下面的问题是，对每个子树计算 $\sum_{x \neq 0} \max \lbrace c_{A,x},c_{B,x} \rbrace$。

体感 Small-to-Large 更好写。

DSU on Tree:

string res(N, '0');
vector<int> cntA(N), cntB(N);
int cur = 0;
auto modify = [&](int x, int delta) {
	if (int v = A[x]; v != -1) {
		cur -= max(cntA[v], cntB[v]);
		cntA[v] += delta;
		cur += max(cntA[v], cntB[v]);
	}
	if (int v = B[x]; v != -1) {
		cur -= max(cntA[v], cntB[v]);
		cntB[v] += delta;
		cur += max(cntA[v], cntB[v]);
	}
};
auto calculate = [&](int x) -> void {
	res[x] = '0' + (cur <= siz[x]);
};

Small-to-Large:

std::vector<int> parent(N, -1), siz(N);
std::vector<std::map<int, std::pair<int, int>>> mp(N);
std::vector<int> cur(N);
std::string res(N, '0');
[&](this auto&& self, int x) -> void {
    if (parent[x] != -1) {
        adj[x].erase(std::ranges::find(adj[x], parent[x]));
    }

    auto add = [&](int v, int dA, int dB) {
        if (v == -1) return;
        auto& [cA, cB] = mp[x][v];
        cur[x] -= std::max(cA, cB);
        cA += dA;
        cB += dB;
        cur[x] += std::max(cA, cB);
    };

    siz[x] = 1;
    for (auto& y : adj[x]) {
        parent[y] = x;
        self(y);
        siz[x] += siz[y];

        // 启发 
        if (mp[x].size() < mp[y].size()) {
            std::swap(mp[x], mp[y]);
            std::swap(cur[x], cur[y]);
        }

        // 合并子树 
        for (auto& [v, _] : mp[y]) {
            auto& [a, b] = _;
            add(v, a, b);
        }
    }

    // 加入当前节点 x 的贡献 
    add(A[x], 1, 0);
    add(B[x], 0, 1);

    // 计算当前节点的答案 
    res[x] = '0' + (cur[x] <= siz[x]);

} (0);