本篇博客參考：

• Oi Wiki 樹上啟發(fā)式合并
• 算法學習筆記(86): 樹上啟發(fā)式合并

基本概念

首先，什么是 啟發(fā)式合并 ？

有人將其稱為“優(yōu)雅的暴力”，啟發(fā)式合并就是在合并兩個部分的時候，將內(nèi)容少的部分合并至內(nèi)容多的部分，減少合并的操作時間

樹上啟發(fā)式合并（dsu on tree） 可以被用來解決樹上的 離線問題（請注意，必須要是離線問題，因為處理問題的順序有講究），特別是可以維護以每個點為根的子樹中的信息

一般來說，對于查詢以每個點為根的子樹中的信息的問題，我們可以用樹形dp來處理，但是如果每個點的信息不止一兩個數(shù)字，而是很龐大的部分（比如說每個點所需要的信息都要多個map來存儲），這樣使用樹形dp的空間復雜度將會非常龐大，而樹上啟發(fā)式合并可以用來解決這樣的問題

代碼實現(xiàn)

舉個例子，比如說我們給出一棵樹，樹上的每個結(jié)點染色，現(xiàn)在我們需要統(tǒng)計以每個結(jié)點為根的子樹中出現(xiàn)多少種顏色

最暴力的方法就是每個結(jié)點跑一次 dfs，用 cnt[] 數(shù)組存儲每個顏色出現(xiàn)的次數(shù)，輸出

但是很明顯會T的很慘

這樣的樹中，我們首先計算2子樹的信息，然后計算3子樹的信息的時候我們又要把2子樹清空，每計算一個新的子樹都要把之前計算過的信息清空，根本存不下來信息啊

然后我們考慮一下怎么優(yōu)化呢，父結(jié)點的信息和子結(jié)點相關(guān)，我們可以用子結(jié)點的信息更新父結(jié)點的信息，也就是，我們在計算1子樹的所有結(jié)點信息時，假如4子樹是234里最后一個被計算的，那我們算完4子樹之后，可以不用清空 cnt 數(shù)組，反正我們計算1子樹的時候還是要遍歷4子樹的，將4子樹的信息全部保留，再加上前面23子樹的信息就可以得到1子樹的信息了

這個4子樹應(yīng)該怎么選擇呢？換句話說，我們保留哪一個子樹的信息不被刪除呢？根據(jù)啟發(fā)式合并的思想，保留最龐大的子樹信息不動，就可以減少重復計算的次數(shù)了

在樹鏈剖分時我們把樹中結(jié)點最多的子樹根結(jié)點叫做重子結(jié)點，也就是說，在樹上啟發(fā)式合并的過程中，我們需要先計算所有輕子結(jié)點的信息（每計算一個輕子結(jié)點之后都要刪除這個結(jié)點對當前答案的影響），最后計算重子結(jié)點的信息（保留重子結(jié)點對當前答案的影響），然后再計算前面的輕子結(jié)點（這一次計算要保留結(jié)點對當前答案的影響）

用兩遍 dfs 實現(xiàn)

下面是一些變量定義：文章來源地址http://www.zghlxwxcb.cn/news/detail-852292.html

• sz[u] 以 u 為根的子樹的結(jié)點數(shù)量
• son[u] 結(jié)點 u 的重子結(jié)點
• col[u] 結(jié)點 u 的顏色
• L[u] 結(jié)點 u 的 dfs 序
• R[u] 以 u 為根的子樹中結(jié)點 dfs 序的最大值
• id[u] L 標號 u 對應(yīng)的結(jié)點編號，有 id[L[u]] == u
• cnt[u] 顏色 u 的出現(xiàn)次數(shù)
• totcol 目前出現(xiàn)過的顏色個數(shù)

void dfs1(int u, int fa) // u: 當前結(jié)點  fa: 父結(jié)點
{
	L[u] = ++ totdfn; // 更新u的dfs序
	Node[totdfn] = u; // 更新dfs序的映射
	sz[u] = 1; // 初始化子樹大小為1
	for (int i = 0; i < g[u].size(); i ++ )
	{
		int j = g[u][i]; // 子結(jié)點編號
		if (j == fa) continue;
		dfs1(j, u);
		sz[u] += sz[j]; // 用子結(jié)點的sz更新父結(jié)點的sz
		if (sz[j] > sz[son[u]]) son[u] = j; // 更新重子結(jié)點
	}
	R[u] = totdfn; // 更新當前子樹中dfs序的最大值
}

void dfs2(int u, int fa, bool keep) // u: 當前結(jié)點  fa: 父結(jié)點  keep: 此次遍歷計算的答案是否保留
{
	// 計算輕子結(jié)點的答案
	for (int i = 0; i < g[u].size(); i ++ )
	{
		int j = g[u][i]; // 子結(jié)點編號
		if (j == fa || j == son[u]) continue; // 遇到重子結(jié)點或者父結(jié)點就跳過
		dfs2(j, u, false); // 繼續(xù)計算輕子結(jié)點的答案且不保留
	}

	if (son[u]) dfs2(son[u], u, true); // 計算重兒子答案并保留計算過程中的數(shù)據(jù)（用于繼承）

	for (int i = 0; i < g[u].size(); i ++ )
	{
		int j = g[u][i]; // 子結(jié)點編號
		if (j == fa || j == son[u]) continue; // 遇到重子結(jié)點或者父結(jié)點就跳過

		// 子樹結(jié)點的 DFS 序構(gòu)成一段連續(xù)區(qū)間，可以直接遍歷
		for (int k = L[j]; k <= R[j]; k ++ ) add(id[k]); // 加上輕子結(jié)點對答案的貢獻
	}
	add(u); // 加上當前子樹根結(jié)點對答案的貢獻
	ans[u] = totcol;
	if (keep == false) // 如果當前計算的答案不保留 就刪去
		for (int i = L[u]; i <= R[u]; i ++ ) del(id[i]);
}

到了這里，關(guān)于【圖論】樹上啟發(fā)式合并的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！