dsu on tree (樹上啟發式合併) 詳解
- 2020 年 11 月 25 日
- 筆記
- dsu on tree, dsu on tree專題
一直都沒出過演算法詳解，昨天心血來潮想寫一篇，於是 dsu on tree 它來了
1、前置技能
1.鏈式前向星（vector 建圖）
2.dfs 建樹
3.剖分輕重鏈，輕重兒子
| 重兒子 | 一個結點的所有兒子中擁有最多子樹的兒子 |
|---|---|
| 輕兒子 | 一個結點的所有兒子中不是重兒子的兒子 |
| 重邊 | 父親與重兒子的連邊 |
| 輕邊 | 父親與輕兒子的連邊 |
| 重鏈 | 一堆重邊連接而成的鏈 |
| 輕鏈 | 一堆輕邊連接而成的鏈 |
2、什麼是 dsu on tree（樹上啟發式合併） ？
dsu on tree 其實就是個優雅的暴力演算法，和它一起共被稱為優雅暴力的演算法還有莫隊
所謂優雅的暴力大概是指：「優雅思想，暴力的操作」
例如莫隊我們知道它是將整個區間分塊，再將詢問的區間排序，最後暴力的維護所有詢問的區間
其中 “整個區間分塊，詢問的區間排序” 為優雅的思想，而 “暴力的維護所有詢問的區間” 為暴力的操作
因為需要將詢問的區間排序，我們就需要先將詢問的區間保存下來，也就是要離線
dsu on tree 和莫隊類似，也需要離線（它們同屬於靜態演算法）
dsu on tree 優雅的思想：
對於以 u 為根的子樹
①. 先統計它輕子樹(輕兒子為根的子樹)的答案，統計完後刪除資訊
②. 再統計它重子樹(重兒子為根的子樹)的答案 ，統計完後保留資訊
③. 然後再將重子樹的資訊合併到 u上
④. 再去遍歷 u 的輕子樹，然後把輕子樹的資訊合併到 u 上
⑤. 判斷 u 的資訊是否需要傳遞給它的父節點（u 是否是它父節點的重兒子）
dsu on tree 暴力的操作
dsu on tree 暴力的操作體現於統計答案上（不同的題目統計方式不一樣）
3、dsu on tree 的過程演示及程式碼
1.圖示
1 的重兒子為 2，輕兒子為 3
2 的重兒子為 4，輕兒子為 5
3 沒有重兒子，沒有輕兒子
4 的重兒子為 6，沒有輕兒子
5 的重兒子為 7，沒有輕兒子
6 沒有重兒子，沒有輕兒子
7 沒有重兒子，沒有輕兒子
為了更好觀看，我們將節點與其重兒子的連線描紅
我們從根節點1進入，先找1的輕兒子，發現3，進入3
3沒有別的兒子可以進入了，於是統計3的資訊
統計完後即將返回父節點 1
因為1-3的邊沒有被描紅邊、3不是1的重兒子（不傳遞3的資訊），所以刪除3的資訊再返回 1
發現1沒有別的輕兒子了，就找重兒子，發現2，進入2
進入2後，再找2的輕兒子，發現5，進入5
發現5沒有輕兒子了，就找重兒子，發現7，進入 7
7 沒有別的兒子可以進入了，於是統計 7 的資訊
統計完後即將返回父節點 5
因為邊5-7 有被描紅邊、7是5的重兒子，所以保留7的資訊直接返回 5（傳遞7的資訊的給5）
5 所有兒子都進入過了，於是統計 5 的資訊
統計完後即將範圍父節點 2
因為邊2-5 沒有被描紅邊、5不是2的重兒子，所以刪除5的資訊再返回 2
發現2沒有其它輕兒子了，就找重兒子，發現4，進入4
發現4沒有其它輕兒子了，就找重兒子，發現6，進入6
6 沒有別的兒子可以進入了，於是統計 6 的資訊
統計完後即將返回父節點 4
因為邊4-6 有被描紅邊，6是4的重兒子，所以保留6的資訊直接返回 4（傳遞6的資訊的給4）
4 所有兒子都進入過了，於是統計 4 的資訊
統計完後即將返回父節點 2
因為邊2-4 有被描紅邊，4是2的重兒子，所以保留4的資訊直接返回2（傳遞4的資訊的給2）
2 所有兒子都進入過了，於是統計 2 的資訊
2 接受了4傳遞的資訊，但是並沒有接受5傳遞給它的資訊（被刪除了）
於是 2 再進入5（輕兒子），統計一遍以 5 為根的子樹的資訊，再將該資訊合併到 2上
統計完後 2 後即將返回父節點 1
因為邊1-2 有被描紅邊，2是1的重兒子，所以保留2的資訊直接返回1（傳遞2的資訊的給1）
1 所有兒子都進入過了，於是統計 1 的資訊
1 接受了2傳遞的資訊，但是並沒有接受3傳遞給它的資訊（被刪除了）
於是 1 再進入3（輕兒子），統計一遍以 3 為根的子樹的資訊，再將該資訊合併到 1 上
至此，整個 dsu on tree 的過程結束
2.程式碼
struct Edge{
int nex , to;
}edge[N << 1];
int head[N] , TOT;
void add_edge(int u , int v) // 鏈式前向星建圖
{
edge[++ TOT].nex = head[u] ;
edge[TOT].to = v;
head[u] = TOT;
}
int sz[N]; // sz[u] 表示以 u 為根的子樹大小
int hson[N]; // hson[u] 表示 u 的重兒子
int HH; // HH 表示當前根節點的重兒子
void dfs(int u , int far)
{
sz[u] = 1;
for(int i = head[u] ; i ; i = edge[i].nex) // 鏈式前向星
{
int v = edge[i].to;
if(v == far) continue ;
dfs(v , u);
sz[u] += sz[v];
if(sz[v] > sz[hson[u]]) hson[u] = v; // 選擇 u 的重兒子
}
}
void calc(int u , int far , int val) // 統計答案
{
if(val == 1) ...; // val = 1，則添加資訊
else ...; // val = -1，則刪除資訊
......
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to;
if(v == far || v == HH) continue ; // 如果 v 是當前根節點的重兒子，則跳過
calc(v , u , val);
}
}
void dsu(int u , int far , int op) // op 等於0表示不保留資訊，等於1表示保留資訊
{
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to;
if(v == far || v == hson[u]) continue ; // 如果 v 是重兒子或者父親節點就跳過
dsu(v , u , 0); // 先遍歷輕兒子 ，op = 0 :輕兒子的答案不做保留
}
if(hson[u]) dsu(hson[u] , u , 1) , HH = hson[u];
// 輕兒子都遍歷完了，如果存在重兒子，遍歷重兒子（事實上除了葉子節點每個點都必然有重兒子）
// op = 1 ， 保留重兒子的資訊
// 當前是以 u 為根節點的子樹，所以根節點的重兒子 HH = hson[u]
calc(u , far , 1); // 再次遍歷輕兒子統計答案
HH = 0; // 遍歷結束 ，即將返回父節點，所以取消標記 HH
if(!op) calc(u , far , -1); // 如果 op = -1，則 u 對於它的父親來說是輕兒子，不需要將資訊傳遞給它的父親
}
4.經典例題講解
5.難題進階
這是道較難的題，聽說這也是 dsu on tree 的發明人專門為這個演算法出的題
| 題目編號 | 題目鏈接 | 題解鏈接 |
|---|---|---|
| CF741D | //codeforces.com/contest/741/problem/D | //www.cnblogs.com/StarRoadTang/p/14028301.html |
┏┛ ┻━━━━━┛ ┻┓
┃ ┃
┃ ━ ┃
┃ ┳┛ ┗┳ ┃
┃ ┃
┃ ┻ ┃
┃ ┃
┗━┓ ┏━━━┛
┃ ┃ 神獸保佑
┃ ┃ 程式碼無BUG！
┃ ┗━━━━━━━━━┓
┃ ┣┓
┃ ┏┛
┗━┓ ┓ ┏━━━┳ ┓ ┏━┛
┃ ┫ ┫ ┃ ┫ ┫
┗━┻━┛ ┗━┻━┛
