跳转至

樹上啓發式合併

引入

啓發式算法是什麼呢？

啓發式算法是基於人類的經驗和直觀感覺，對一些算法的優化。

給個例子？

最常見的就是並查集的按秩合併了，有帶按秩合併的並查集中，合併的代碼是這樣的：

1
2
3
4
5
6
void merge(int x, int y) {
  int xx = find(x), yy = find(y);
  if (size[xx] < size[yy]) swap(xx, yy);
  fa[yy] = xx;
  size[xx] += size[yy];
}

在這裏，對於兩個大小不一樣的集合，我們將小的集合合併到大的集合中，而不是將大的集合合併到小的集合中。

為什麼呢？這個集合的大小可以認為是集合的高度（在正常情況下），而我們將集合高度小的併到高度大的顯然有助於我們找到父親

讓高度小的樹成為高度較大的樹的子樹，這個優化可以稱為啓發式合併算法。

算法內容

樹上啓發式合併（dsu on tree）對於某些樹上離線問題可以速度大於等於大部分算法且更易於理解和實現的算法。

考慮下面的問題：樹上數顏色

例題引入

給出一棵 \(n\) 個節點以 \(1\) 為根的樹，節點 \(u\) 的顏色為 \(c_u\)，現在對於每個結點 \(u\) 詢問 \(u\) 子樹裏一共出現了多少種不同的顏色。

\(n\le 2\times 10^5\)。

dsu-on-tree-1.png

對於這種問題解決方式大多是運用大量的數據結構（樹套樹等），如果可以離線，詢問的量巨大，是不是有更簡單的方法？

樹上莫隊！

不行，莫隊帶根號，我要 log

過程

既然支持離線，考慮預處理後 \(O(1)\) 輸出答案。

直接暴力預處理的時間複雜度為 \(O(n^2)\)，即對每一個子節點進行一次遍歷，每次遍歷的複雜度顯然與 \(n\) 同階，有 \(n\) 個節點，故複雜度為 \(O(n^2)\)。

可以發現，每個節點的答案由其子樹和其本身得到，考慮利用這個性質處理問題。

我們可以先預處理出每個節點子樹的大小和它的重兒子，重兒子同樹鏈剖分一樣，是擁有節點最多子樹的兒子，這個過程顯然可以 \(O(n)\) 完成

我們用 cnt[i] 表示顏色 \(i\) 的出現次數，ans[u] 表示結點 \(u\) 的答案。

遍歷一個節點 \(u\)，我們按以下的步驟進行遍歷：

  1. 先遍歷 \(u\) 的輕（非重）兒子，並計算答案，但 不保留遍歷後它對 cnt 數組的影響；
  2. 遍歷它的重兒子，保留它對 cnt 數組的影響；
  3. 再次遍歷 \(u\) 的輕兒子的子樹結點，加入這些結點的貢獻，以得到 \(u\) 的答案。

dsu-on-tree-2.png

上圖是一個例子。

這樣，對於一個節點，我們遍歷了一次重子樹，兩次非重子樹，顯然是最划算的。

通過執行這個過程，我們獲得了這個節點所有子樹的答案。

為什麼不合並第一步和第三步呢？因為 cnt 數組不能重複使用，否則空間會太大，需要在 \(O(n)\) 的空間內完成。

顯然若一個節點 \(u\) 被遍歷了 \(x\) 次，則其重兒子會被遍歷 \(x\) 次，輕兒子（如果有的話）會被遍歷 \(2x\) 次。

注意除了重兒子，每次遍歷完 cnt 要清零。

證明

（對於不關心複雜度證明的，可以跳過不看）

我們像樹鏈剖分一樣定義重邊和輕邊（連向重兒子的為重邊，其餘為輕邊）關於重兒子和重邊的定義，可以見下圖，對於一棵有 \(n\) 個節點的樹：

根節點到樹上任意節點的輕邊數不超過 \(\log n\) 條。我們設根到該節點有 x 條輕邊該節點的子樹大小為 \(y\)，顯然輕邊連接的子節點的子樹大小小於父親的一半（若大於一半就不是輕邊了），則 \(y<n/2^x\)，顯然 \(n>2^x\)，所以 \(x<\log n\)。

又因為如果一個節點是其父親的重兒子，則它的子樹必定在它的兄弟之中最多，所以任意節點到根的路徑上所有重邊連接的父節點在計算答案時必定不會遍歷到這個節點，所以一個節點的被遍歷的次數等於它到根節點路徑上的輕邊數 \(+1\)（之所以要 \(+1\) 是因為它本身要被遍歷到），所以一個節點的被遍歷次數 \(=\log n+1\), 總時間複雜度則為 \(O(n(\log n+1))=O(n\log n)\)，輸出答案花費 \(O(m)\).

dsu-on-tree-3.png

圖中標粗的即為重邊，重邊連向的子節點為重兒子

實現

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n;

// g[u]: 存儲與 u 相鄰的結點
vector<int> g[N];

// sz: 子樹大小
// big: 重兒子
// col: 結點顏色
// L[u]: 結點 u 的 DFS 序
// R[u]: 結點 u 子樹中結點的 DFS 序的最大值
// Node[i]: DFS 序為 i 的結點
// ans: 存答案
// cnt[i]: 顏色為 i 的結點個數
// totColor: 目前出現過的顏色個數
int sz[N], big[N], col[N], L[N], R[N], Node[N], totdfn;
int ans[N], cnt[N], totColor;

void add(int u) {
  if (cnt[col[u]] == 0) ++totColor;
  cnt[col[u]]++;
}

void del(int u) {
  cnt[col[u]]--;
  if (cnt[col[u]] == 0) --totColor;
}

int getAns() { return totColor; }

void dfs0(int u, int p) {
  L[u] = ++totdfn;
  Node[totdfn] = u;
  sz[u] = 1;
  for (int v : g[u])
    if (v != p) {
      dfs0(v, u);
      sz[u] += sz[v];
      if (!big[u] || sz[big[u]] < sz[v]) big[u] = v;
    }
  R[u] = totdfn;
}

void dfs1(int u, int p, bool keep) {
  // 計算輕兒子的答案
  for (int v : g[u])
    if (v != p && v != big[u]) {
      dfs1(v, u, false);
    }
  // 計算重兒子答案並保留計算過程中的數據（用於繼承）
  if (big[u]) {
    dfs1(big[u], u, true);
  }
  for (int v : g[u])
    if (v != p && v != big[u]) {
      // 子樹結點的 DFS 序構成一段連續區間，可以直接遍歷
      for (int i = L[v]; i <= R[v]; i++) {
        add(Node[i]);
      }
    }
  add(u);
  ans[u] = getAns();
  if (keep == false) {
    for (int i = L[u]; i <= R[u]; i++) {
      del(Node[i]);
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs0(1, 0);
  dfs1(1, 0, false);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]);
  return 0;
}

運用

  1. 某些出題人設置的正解是 dsu on tree 的題

    如 CF741D。給一棵樹，每個節點的權值是'a' 到'v' 的字母，每次詢問要求在一個子樹找一條路徑，使該路徑包含的字符排序後成為迴文串。

    因為是排列後成為迴文串，所以一個字符出現了兩次相當於沒出現，也就是説，這條路徑滿足 最多有一個字符出現奇數次。

    正常做法是對每一個節點 dfs，每到一個節點就強行枚舉所有字母找到和它異或後結果為 1 的個數大於 1 的路徑，再取最長值，這樣是 \(O(n^2\log n)\) 的，可以用 dsu on tree 優化到 \(O(n\log^2n)\)。關於具體做法，可以參考下面的擴展閲讀

  2. 可以用 dsu 亂搞的題

    可以水一些樹套樹的部分分（沒有修改操作），而且 dsu 的複雜度優於樹上莫隊的 \(O(n\sqrt{m})\)

練習題

CF600E Lomsat gelral

題意翻譯：樹的節點有顏色，一種顏色佔領了一個子樹，當且僅當沒有其他顏色在這個子樹中出現得比它多。求佔領每個子樹的所有顏色之和。

UOJ284 快樂遊戲雞

CF1709E XOR Tree

參考資料/擴展閲讀

CF741D 作者介紹的 dsu on tree

這位作者的題解

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：abc1763613206, cesonic, Ir1d, MingqiHuang, xinchengo
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用