Bỏ qua

Phân tách Heavy-Light

Giới thiệu

Phân tích chuỗi nặng nhẹ (Heavy-Light Decomposition, viết tắt HLD) là kỹ thuật chia cây thành các chuỗi để dễ dàng quản lý thông tin trên đường đi trong cây.

Cụ thể, HLD chia cây thành nhiều chuỗi, kết hợp thành cấu trúc tuyến tính, sau đó dùng các cấu trúc dữ liệu khác để quản lý thông tin.

Phân tích chuỗi nặng nhẹ (còn gọi là "phân tích chuỗi", "phân tích đường") có nhiều biến thể như phân tích chuỗi nặng (heavy chain), phân tích chuỗi dài (long chain), và phân tích dùng cho Link/Cut Tree (đôi khi gọi là "phân tích chuỗi thực"). Nếu không nói rõ, "phân tích chuỗi" thường chỉ "phân tích chuỗi nặng".

Phân tích chuỗi nặng nhẹ đảm bảo mọi đường đi trên cây có thể chia thành không quá \(O(\log n)\) chuỗi liên tiếp, các đỉnh trên mỗi chuỗi có độ sâu khác nhau (chuỗi đi từ dưới lên, LCA của chuỗi là một đầu mút).

HLD còn đảm bảo các đỉnh trên mỗi chuỗi có thứ tự DFS liên tiếp, nên có thể dùng các cấu trúc dữ liệu quản lý dãy số (như segment tree) để quản lý thông tin đường đi. Ví dụ:

  1. Cập nhật giá trị các đỉnh trên đường đi giữa hai đỉnh bất kỳ.
  2. Truy vấn tổng/giá trị lớn nhất/các thông tin khác trên đường đi giữa hai đỉnh bất kỳ (miễn là có thể quản lý trên dãy số).

Ngoài việc phối hợp với cấu trúc dữ liệu để quản lý đường đi, HLD còn có thể dùng để tìm LCA trong \(O(\log n)\) (với hằng số nhỏ). Một số bài toán còn tận dụng các tính chất đặc biệt của HLD.

Phân tích chuỗi nặng

Một số định nghĩa:

  • Con nặng của một đỉnh là con có cây con lớn nhất. Nếu có nhiều con cùng lớn nhất, chọn một. Nếu không có con, không có con nặng.
  • Con nhẹ là các con còn lại.
  • Cạnh nối tới con nặng gọi là cạnh nặng.
  • Cạnh nối tới con nhẹ gọi là cạnh nhẹ.
  • Nhiều cạnh nặng nối tiếp tạo thành chuỗi nặng.
  • Đỉnh lẻ cũng coi là chuỗi nặng, nên toàn bộ cây được chia thành nhiều chuỗi nặng.

Minh họa:

HLD

Cài đặt

HLD gồm hai lần DFS. Pseudocode:

DFS đầu tiên ghi nhận cha (\(\textit{father}\)), độ sâu (\(\textit{depth}\)), kích thước cây con (\(\textit{size}\)), con nặng (\(\textit{hson}\)).

\[ \begin{array}{l} \text{TREE-BUILD }(u,\textit{dep}) \\ \begin{array}{ll} 1 & u.\textit{hson}\gets 0 \\ 2 & u.\textit{hson}.\textit{size}\gets 0 \\ 3 & u.\textit{depth}\gets \textit{dep} \\ 4 & u.\textit{size}\gets 1 \\ 5 & \textbf{for }\text{each son }v\text{ of }u \\ 6 & \qquad u.\textit{size}\gets u.\textit{size} + \text{TREE-BUILD }(v,\textit{dep}+1) \\ 7 & \qquad v.\textit{father}\gets u \\ 8 & \qquad \textbf{if }v.\textit{size}> u.\textit{hson}.\textit{size} \\ 9 & \qquad \qquad u.\textit{hson}\gets v \\ 10 & \textbf{return } u.\textit{size} \end{array} \end{array} \]

DFS thứ hai ghi nhận đỉnh đầu chuỗi (\(\textit{top}\), khởi tạo là chính nó), thứ tự DFS khi duyệt chuỗi nặng (\(\textit{top}\)), và ánh xạ thứ tự DFS sang đỉnh (\(\textit{rank}\)).

\[ \begin{array}{l} \text{TREE-DECOMPOSITION }(u,\textit{top}) \\ \begin{array}{ll} 1 & u.\textit{top}\gets \textit{top} \\ 2 & \textit{tot}\gets \textit{tot}+1\\ 3 & u.\textit{dfn}\gets \textit{tot} \\ 4 & \textit{rank}(\textit{tot})\gets u \\ 5 & \textbf{if }u.\textit{hson}\text{ is not }0 \\ 6 & \qquad \text{TREE-DECOMPOSITION }(u.\textit{hson},\textit{top}) \\ 7 & \qquad \textbf{for }\text{each son }v\text{ of }u \\ 8 & \qquad \qquad \textbf{if }v\text{ is not }u.\textit{hson} \\ 9 & \qquad \qquad \qquad \text{TREE-DECOMPOSITION }(v,v) \end{array} \end{array} \]

Mã tham khảo:

  • \(\operatorname{fa}(x)\): cha của \(x\).
  • \(\operatorname{dep}(x)\): độ sâu của \(x\).
  • \(\operatorname{siz}(x)\): kích thước cây con của \(x\).
  • \(\operatorname{son}(x)\): con nặng của \(x\).
  • \(\operatorname{top}(x)\): đầu chuỗi nặng chứa \(x\).
  • \(\operatorname{dfn}(x)\): thứ tự DFS của \(x\), cũng là vị trí trên segment tree.
  • \(\operatorname{rnk}(x)\): ánh xạ từ thứ tự DFS sang đỉnh, \(\operatorname{rnk}(\operatorname{dfn}(x))=x\).

Hai lần DFS: lần 1 tính \(\operatorname{fa}(x)\), \(\operatorname{dep}(x)\), \(\operatorname{siz}(x)\), \(\operatorname{son}(x)\); lần 2 tính \(\operatorname{top}(x)\), \(\operatorname{dfn}(x)\), \(\operatorname{rnk}(x)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void dfs1(int u, int f) {
  fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
  for (auto v : G[u]) {
    if (v == f) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}

void dfs2(int u, int ftop) {
  top[u] = ftop, dfn[u] = ++idx, rnk[idx] = u;
  if (son[u]) dfs2(son[u], ftop);
  for (auto v : G[u])
    if (v != son[u] && v != fa[u]) dfs2(v, v);
}

Tính chất của phân tích chuỗi nặng

Mỗi đỉnh thuộc duy nhất một chuỗi nặng.

Đầu chuỗi nặng không nhất thiết là con nặng (vì cạnh nặng xác định cho từng đỉnh).

Các chuỗi nặng chia cây thành các chuỗi không giao nhau.

Khi duyệt chuỗi nặng trước, thứ tự DFS trên chuỗi là liên tiếp. Sắp xếp theo DFN sẽ ra chuỗi.

Thứ tự DFS của cây con là liên tiếp.

Khi đi qua một cạnh nhẹ, kích thước cây con giảm ít nhất một nửa.

Với mọi đường đi trên cây, chia thành hai đoạn từ LCA xuống hai đầu, mỗi đoạn đi qua tối đa \(O(\log n)\) chuỗi nặng.

Làm sao để kiểm tra HLD có thực sự \(O(\log n)\)?

Thường thì hằng số của HLD rất nhỏ, khó kiểm tra. Nếu muốn kiểm tra, có thể xây cây nhị phân có độ sâu thấp.

Có thể dùng phương pháp trung gian.

Xây cây nhị phân \(\sqrt{n}\) đỉnh, mỗi cạnh nối tới con thay bằng chuỗi dài \(\sqrt{n}\).

Như vậy, số lần chuyển chuỗi khi truy vấn ngẫu nhiên là trung bình \(\frac{\log n}{2}\), độ sâu \(O(\sqrt{n} \log n)\).

Thêm một số lá ngẫu nhiên có thể kiểm tra HLD. Tuy nhiên, hằng số nhỏ nên khó kiểm tra.

Ứng dụng phổ biến

Quản lý đường đi

Dùng HLD để tính tổng trọng số trên đường đi giữa hai đỉnh, pseudocode:

\[ \begin{array}{l} \text{TREE-PATH-SUM }(u,v) \\ \begin{array}{ll} 1 & \textit{tot}\gets 0 \\ 2 & \textbf{while }u.\textit{top}\text{ is not }v.\textit{top} \\ 3 & \qquad \textbf{if }u.\textit{top}.\textit{depth}< v.\textit{top}.\textit{depth} \\ 4 & \qquad \qquad \text{SWAP}(u, v) \\ 5 & \qquad \textit{tot}\gets \textit{tot} + \text{sum of values between }u\text{ and }u.\textit{top} \\ 6 & \qquad u\gets u.\textit{top}.\textit{father} \\ 7 & \textit{tot}\gets \textit{tot} + \text{sum of values between }u\text{ and }v \\ 8 & \textbf{return } \textit{tot} \end{array} \end{array} \]

Thứ tự DFS trên chuỗi là liên tiếp, có thể dùng segment tree, BIT để quản lý.

Mỗi lần nhảy lên chuỗi có độ sâu lớn hơn, đến khi hai đỉnh cùng chuỗi.

Cách nhảy chuỗi này cũng dùng cho các truy vấn khác trên đường đi.

Quản lý thông tin cây con

Đôi khi cần quản lý thông tin trên cây con, ví dụ tăng trọng số mọi đỉnh trong cây con gốc \(x\).

Khi DFS, thứ tự DFS của cây con là liên tiếp.

Mỗi đỉnh lưu bottom là đỉnh cuối cùng của cây con trên DFS.

Như vậy, thông tin cây con chuyển thành một đoạn liên tiếp.

Tìm LCA

Nhảy lên chuỗi nặng, khi hai đỉnh cùng chuỗi, đỉnh có độ sâu nhỏ hơn là LCA.

Khi nhảy, luôn nhảy chuỗi có độ sâu lớn hơn.

Mã tham khảo:

1
2
3
4
5
6
7
8
9
int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]])
      u = fa[top[u]];
    else
      v = fa[top[v)];
  }
  return dep[u] > dep[v] ? v : u;
}

Đổi gốc

Xét bài toán: ngoài các thao tác cơ bản, còn có thao tác đổi gốc.

Vì HLD quản lý thông tin tĩnh, không hỗ trợ cập nhật động. Không thể mỗi lần đổi gốc lại tiền xử lý, quá tốn thời gian. Cần tận dụng thông tin đã có.

Với truy vấn đường đi, vì đường đi giữa hai đỉnh là duy nhất, không bị ảnh hưởng, xử lý như bình thường.

Với truy vấn cây con, cần ánh xạ cây con sau khi đổi gốc về cây con ban đầu. Phải xét vị trí của gốc mới, gốc cũ và đỉnh truy vấn. Chi tiết xem phần ví dụ.

Ví dụ

Dưới đây là một số ví dụ ứng dụng HLD. Đầu tiên là bài mẫu.

「ZJOI2008」Thống kê trên cây

Cho cây \(n\) đỉnh có trọng số, thực hiện \(q\) thao tác:

  1. Đổi trọng số một đỉnh;
  2. Truy vấn giá trị lớn nhất trên đường đi giữa hai đỉnh;
  3. Truy vấn tổng trọng số trên đường đi giữa hai đỉnh.

\(1\le n\le 30000\), \(0\le q\le 200000\).

Giải thích

Theo đề và các tính chất trên, segment tree cần hỗ trợ:

  1. Đổi trọng số một đỉnh;
  2. Truy vấn giá trị lớn nhất trên đoạn;
  3. Truy vấn tổng trên đoạn.

Đổi trọng số một đỉnh rất dễ.

Vì thứ tự DFS của cây con là liên tiếp (không cần HLD), đổi trọng số cây con chỉ cần cập nhật đoạn liên tiếp.

Vấn đề là làm sao cập nhật/truy vấn đường đi giữa hai đỉnh.

Xét cách tìm LCA bằng phương pháp nhảy bậc: đưa hai đỉnh lên cùng độ sâu, rồi nhảy lên cùng nhau. Với HLD cũng vậy.

Khi nhảy, nếu đang ở chuỗi nặng, nhảy lên đầu chuỗi; nếu không, nhảy lên một đỉnh. Lặp lại đến khi hai đỉnh trùng nhau. Cập nhật/truy vấn trên đoạn tương ứng.

Mỗi truy vấn đi qua tối đa \(O(\log n)\) chuỗi nặng, mỗi chuỗi truy vấn segment tree \(O(\log n)\), tổng \(O(n\log n+q\log^2 n)\). Thực tế số chuỗi nặng khó đạt \(O(\log n)\) (chỉ khi cây nhị phân đầy), nên HLD thường có hằng số nhỏ.

Mã tham khảo 
  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <algorithm>
#include <cstring>
#include <iostream>
#define lc o << 1
#define rc o << 1 | 1
constexpr int MAXN = 60010;
constexpr int inf = 2e9;
int n, a, b, w[MAXN], q, u, v;
int cur, h[MAXN], nxt[MAXN], p[MAXN];
int siz[MAXN], top[MAXN], son[MAXN], dep[MAXN], fa[MAXN], dfn[MAXN], rnk[MAXN],
    cnt;
char op[10];

void add_edge(int x, int y) {  // 加边
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
}

struct SegTree {
  int sum[MAXN * 4], maxx[MAXN * 4];

  void build(int o, int l, int r) {
    if (l == r) {
      sum[o] = maxx[o] = w[rnk[l]];
      return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    sum[o] = sum[lc] + sum[rc];
    maxx[o] = std::max(maxx[lc], maxx[rc]);
  }

  int query1(int o, int l, int r, int ql, int qr) {  // 查询 max
    if (l > qr || r < ql) return -inf;
    if (ql <= l && r <= qr) return maxx[o];
    int mid = (l + r) >> 1;
    return std::max(query1(lc, l, mid, ql, qr), query1(rc, mid + 1, r, ql, qr));
  }

  int query2(int o, int l, int r, int ql, int qr) {  // 查询 sum
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[o];
    int mid = (l + r) >> 1;
    return query2(lc, l, mid, ql, qr) + query2(rc, mid + 1, r, ql, qr);
  }

  void update(int o, int l, int r, int x, int t) {  // 更新
    if (l == r) {
      maxx[o] = sum[o] = t;
      return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
      update(lc, l, mid, x, t);  // 左右分别更新
    else
      update(rc, mid + 1, r, x, t);
    sum[o] = sum[lc] + sum[rc];
    maxx[o] = std::max(maxx[lc], maxx[rc]);
  }
} st;

void dfs1(int o) {
  son[o] = -1;
  siz[o] = 1;
  for (int j = h[o]; j; j = nxt[j])
    if (!dep[p[j]]) {
      dep[p[j]] = dep[o] + 1;
      fa[p[j]] = o;
      dfs1(p[j]);
      siz[o] += siz[p[j]];
      if (son[o] == -1 || siz[p[j]] > siz[son[o]]) son[o] = p[j];
    }
}

void dfs2(int o, int t) {
  top[o] = t;
  cnt++;
  dfn[o] = cnt;
  rnk[cnt] = o;
  if (son[o] == -1) return;
  dfs2(son[o], t);
  for (int j = h[o]; j; j = nxt[j])
    if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}

int querymax(int x, int y) {  // 查询，看main函数理解一下
  int ret = -inf, fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] >= dep[fy])
      ret = std::max(ret, st.query1(1, 1, n, dfn[fx], dfn[x])), x = fa[fx];
    else
      ret = std::max(ret, st.query1(1, 1, n, dfn[fy], dfn[y])), y = fa[fy];
    fx = top[x];
    fy = top[y];
  }
  if (dfn[x] < dfn[y])
    ret = std::max(ret, st.query1(1, 1, n, dfn[x], dfn[y]));
  else
    ret = std::max(ret, st.query1(1, 1, n, dfn[y], dfn[x]));
  return ret;
}

int querysum(int x, int y) {
  int ret = 0, fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] >= dep[fy])
      ret += st.query2(1, 1, n, dfn[fx], dfn[x]), x = fa[fx];
    else
      ret += st.query2(1, 1, n, dfn[fy], dfn[y]), y = fa[fy];
    fx = top[x];
    fy = top[y];
  }
  if (dfn[x] < dfn[y])
    ret += st.query2(1, 1, n, dfn[x], dfn[y]);
  else
    ret += st.query2(1, 1, n, dfn[y], dfn[x]);
  return ret;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i < n; i++) cin >> a >> b, add_edge(a, b), add_edge(b, a);
  for (int i = 1; i <= n; i++) cin >> w[i];
  dep[1] = 1;
  dfs1(1);
  dfs2(1, 1);
  st.build(1, 1, n);
  cin >> q;
  while (q--) {
    cin >> op >> u >> v;
    if (!strcmp(op, "CHANGE")) st.update(1, 1, n, dfn[u], v);
    if (!strcmp(op, "QMAX")) cout << querymax(u, v) << '\n';
    if (!strcmp(op, "QSUM")) cout << querysum(u, v) << '\n';
  }
  return 0;
}

Tiếp theo là bài mẫu có đổi gốc.

LOJ 139. Phân tích chuỗi trên cây

Cho cây \(n\) đỉnh (gốc ban đầu là \(1\)), thực hiện \(m\) thao tác:

  • Đổi gốc, đặt \(u\) làm gốc mới;
  • Tăng trọng số các đỉnh trên đường đi giữa \(u\) và \(v\) lên \(w\);
  • Tăng trọng số các đỉnh trong cây con gốc \(u\) lên \(w\);
  • Truy vấn tổng trọng số các đỉnh trên đường đi giữa \(u\) và \(v\);
  • Truy vấn tổng trọng số các đỉnh trong cây con gốc \(u\).

\(1 \le n,m \le 10^5\).

Giải thích

Tiền xử lý DFS với gốc \(1\), lưu thông tin HLD. Gọi cây gốc \(1\) là "cây gốc", cây sau khi đổi gốc là "cây hiện tại". Khi thao tác, cần ánh xạ truy vấn/cập nhật về cây gốc.

Đổi gốc: gán \(\textit{root}\gets u\). Truy vấn/cập nhật đường đi: không bị ảnh hưởng, xử lý như bình thường.

Truy vấn/cập nhật cây con: cần xét vị trí của \(u\) và \(\textit{root}\) trên cây gốc:

  • \(u = \textit{root}\): thao tác trên toàn bộ cây, cập nhật/truy vấn segment tree gốc.

  • \(u\) là tổ tiên của \(\textit{root}\) trên cây gốc (nằm trên đường từ \(1\) tới \(\textit{root}\)):

    Trường hợp này cần chú ý. Gọi \(v\) là đỉnh trên đường từ \(u\) tới \(\textit{root}\) (trừ \(u\)) có độ sâu nhỏ nhất. Khi đó, phần ngoài cây con gốc \(v\) trên cây gốc chính là cây con gốc \(u\) trên cây hiện tại.

    Làm sao tìm \(v\)? Đầu tiên gán \(v\gets\textit{root}\), rồi nhảy lên chuỗi nặng cho tới khi \(\operatorname{dep}(\operatorname{top}(v))\le\operatorname{dep}(u)+1\).

    • Nếu \(\operatorname{dep}(\operatorname{top}(v))=\operatorname{dep}(u)+1\), gán \(v\gets\operatorname{top}(v)\), tức \(v\) là con nhẹ của \(u\).
    • Nếu \(\operatorname{dep}(\operatorname{top}(v))<\operatorname{dep}(u)+1\), tức \(u,v\) cùng chuỗi nặng, \(v\) có \(\operatorname{dfn}(v)=\operatorname{dfn}(u)+1\), nên gán \(v\gets\operatorname{rnk}(\operatorname{dfn}(u)+1)\).

    Hai trường hợp này có thể gộp: sau khi nhảy, gán

    \[ v\gets\operatorname{rnk}(\operatorname{dfn}(\operatorname{top}(v))+\operatorname{dep}(u)+1-\operatorname{dep}(\operatorname{top}(v))). \]

    Có thể kiểm chứng \(v\) tìm được như trên là đúng. Mã tham khảo cũng dùng cách này.

    Vì cây con gốc \(v\) là đoạn \([\operatorname{dfn}(v),\operatorname{dfn}(v)+\operatorname{siz}(v))\), nên chỉ cần thao tác trên \([1,\operatorname{dfn}(v))\cup[\operatorname{dfn}(v)+\operatorname{siz}(v),n]\).

  • Trường hợp khác: thao tác trên cây con gốc \(u\) như bình thường.

Độ phức tạp như không đổi gốc, \(O(n\log^2 n)\).

Mã tham khảo 
  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <vector>

using lint = long long;
constexpr int N = 1e5 + 10;

int n, m, root, a[N];
std::vector<int> G[N];

int idx, fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N];

struct SegmentTree {  // 区间加，区间求和的线段树实现
  lint sum[N << 2], lzy[N << 2];

  void maketag(int u, int l, int r, lint x) {
    sum[u] += (r - l + 1) * x;
    lzy[u] += x;
  }

  void pushup(int u) { sum[u] = sum[u << 1] + sum[u << 1 | 1]; }

  void pushdown(int u, int l, int r) {
    int mid = l + r >> 1;
    maketag(u << 1, l, mid, lzy[u]);
    maketag(u << 1 | 1, mid + 1, r, lzy[u]);
    lzy[u] = 0;
  }

  void build(int u, int l, int r) {
    if (l == r) {
      sum[u] = a[rnk[l]];
      return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }

  void upd(int u, int l, int r, int ql, int qr, lint x) {
    if (ql <= l && r <= qr) {
      maketag(u, l, r, x);
      return;
    }
    int mid = l + r >> 1;
    pushdown(u, l, r);
    if (ql <= mid) upd(u << 1, l, mid, ql, qr, x);
    if (qr > mid) upd(u << 1 | 1, mid + 1, r, ql, qr, x);
    pushup(u);
  }

  lint ask(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum[u];
    int mid = l + r >> 1;
    pushdown(u, l, r);
    if (qr <= mid) return ask(u << 1, l, mid, ql, qr);
    if (ql > mid) return ask(u << 1 | 1, mid + 1, r, ql, qr);
    return ask(u << 1, l, mid, ql, qr) + ask(u << 1 | 1, mid + 1, r, ql, qr);
  }
} T;

void dfs1(int u, int f) {  // 树剖预处理 1
  fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
  for (auto v : G[u]) {
    if (v == f) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}

void dfs2(int u, int tp) {  // 树剖预处理 2
  top[u] = tp, dfn[u] = ++idx, rnk[idx] = u;
  if (son[u]) dfs2(son[u], tp);
  for (auto v : G[u])
    if (v != fa[u] && v != son[u]) dfs2(v, v);
}

void modify_path(int u, int v, int w) {  // 正常树剖
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
    T.upd(1, 1, n, dfn[top[u]], dfn[u], w);
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) std::swap(u, v);
  T.upd(1, 1, n, dfn[v], dfn[u], w);
}

void modify_subtree(int u, int w) {
  if (u == root)
    T.maketag(1, 1, n, w);
  else if (dfn[u] <= dfn[root] && dfn[root] <= dfn[u] + siz[u] - 1) {
    int v = root;
    while (dep[top[v]] > dep[u] + 1) v = fa[top[v]];  // 向上跳
    v = rnk[dfn[top[v]] + dep[u] + 1 - dep[top[v]]];  // 计算 v
    // 上面这一句可以替换为如下两句：
    // if (dep[top[v]] == dep[u] + 1) v = top[v];
    // else if (dep[top[v]] < dep[u] + 1) v = rnk[dfn[u] + 1];
    if (1 <= dfn[v] - 1) T.upd(1, 1, n, 1, dfn[v] - 1, w);
    if (dfn[v] + siz[v] <= n) T.upd(1, 1, n, dfn[v] + siz[v], n, w);
  } else
    T.upd(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, w);
}

lint query_path(int u, int v) {  // 正常树剖
  lint res = 0;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
    res += T.ask(1, 1, n, dfn[top[u]], dfn[u]);
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) std::swap(u, v);
  res += T.ask(1, 1, n, dfn[v], dfn[u]);
  return res;
}

lint query_subtree(int u) {
  if (u == root) return T.sum[1];
  if (dfn[u] <= dfn[root] && dfn[root] <= dfn[u] + siz[u] - 1) {
    int v = root;
    while (dep[top[v]] > dep[u] + 1) v = fa[top[v]];
    v = rnk[dfn[top[v]] + dep[u] + 1 - dep[top[v]]];
    lint res = 0;
    if (1 <= dfn[v] - 1) res += T.ask(1, 1, n, 1, dfn[v] - 1);
    if (dfn[v] + siz[v] <= n) res += T.ask(1, 1, n, dfn[v] + siz[v], n);
    return res;
  }
  return T.ask(1, 1, n, dfn[u], dfn[u] + siz[u] - 1);
}

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cin >> n, root = 1;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 2, f; i <= n; ++i) {
    std::cin >> f;
    G[i].emplace_back(f);
    G[f].emplace_back(i);
  }
  dfs1(1, 0), dfs2(1, 1), T.build(1, 1, n);  // 预处理
  for (std::cin >> m; m; --m) {
    int op, u, v, w;
    std::cin >> op >> u;
    if (op == 1)
      root = u;  // 换根
    else if (op == 2)
      std::cin >> v >> w, modify_path(u, v, w);  // 修改路径
    else if (op == 3)
      std::cin >> w, modify_subtree(u, w);  // 修改子树
    else if (op == 4)
      std::cin >> v, std::cout << query_path(u, v) << "\n";  // 查询路径
    else
      std::cout << query_subtree(u) << "\n";  // 查询子树
  }
  std::cout.flush();
  return 0;
}

Cuối cùng là một bài tương tác, ứng dụng đặc biệt của HLD.

Nauuo và cây nhị phân

Cho cây nhị phân gốc \(1\), bạn có thể hỏi khoảng cách giữa hai đỉnh bất kỳ, yêu cầu xác định cha của mỗi đỉnh.

Số đỉnh không quá \(3000\), tối đa \(30000\) truy vấn.

Giải thích

Đầu tiên hỏi \(n-1\) lần để xác định độ sâu từng đỉnh.

Sau đó, duyệt theo thứ tự tăng dần độ sâu để xác định cha từng đỉnh, khi đó các tổ tiên đều đã biết.

Trước khi xác định cha một đỉnh, xây HLD cho phần cây đã biết.

Giả sử cần tìm vị trí của đỉnh \(k\) trong cây con gốc \(u\), hỏi khoảng cách giữa \(k\) và đỉnh cuối chuỗi nặng gốc \(u\), xác định vị trí \(k\) như hình:

Đường đỏ là chuỗi nặng, \(d\) là kết quả truy vấn \(\textit{dis}(k, \textit{bot}(u))\), độ sâu \(v\) là \((\textit{dep}(k)+\textit{dep}(\textit{bot}(u))-d)/2\).

Nếu \(v\) có một con, cha của \(k\) là \(v\), nếu không thì đệ quy tìm trong cây con gốc \(w\).

Độ phức tạp \(O(n^2)\), số truy vấn \(O(n\log n)\).

Gọi \(T(n)\) là số truy vấn tối đa để tìm vị trí một đỉnh mới trong cây \(n\) đỉnh:

\[ T(n)\le \begin{cases} 0&n=1\\ T\left(\left\lfloor\frac{n-1}2\right\rfloor\right)+1&n\ge2 \end{cases} \]

\(2999+\sum_{i=1}^{2999}T(i)\le 29940\), thực tế có thể đạt được nếu dữ liệu xấu, nhưng nếu thêm một chút ngẫu nhiên (ví dụ sắp xếp độ sâu không ổn định), số truy vấn khó vượt quá \(21000\).

Mã tham khảo 
 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
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

constexpr int N = 3010;

int n, fa[N], ch[N][2], dep[N], siz[N], son[N], bot[N], id[N];

int query(int u, int v) {
  printf("? %d %d\n", u, v);
  fflush(stdout);
  int d;
  scanf("%d", &d);
  return d;
}

void setFather(int u, int v) {
  fa[v] = u;
  if (ch[u][0])
    ch[u][1] = v;
  else
    ch[u][0] = v;
}

void dfs(int u) {
  if (ch[u][0]) dfs(ch[u][0]);
  if (ch[u][1]) dfs(ch[u][1]);

  siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1;

  if (ch[u][1])
    son[u] = int(siz[ch[u][0]] < siz[ch[u][1]]);
  else
    son[u] = 0;

  if (ch[u][son[u]])
    bot[u] = bot[ch[u][son[u]]];
  else
    bot[u] = u;
}

void solve(int u, int k) {
  if (!ch[u][0]) {
    setFather(u, k);
    return;
  }
  int d = query(k, bot[u]);
  int v = bot[u];
  while (dep[v] > (dep[k] + dep[bot[u]] - d) / 2) v = fa[v];
  int w = ch[v][son[v] ^ 1];
  if (w)
    solve(w, k);
  else
    setFather(v, k);
}

int main() {
  int i;

  scanf("%d", &n);

  for (i = 2; i <= n; ++i) {
    id[i] = i;
    dep[i] = query(1, i);
  }

  sort(id + 2, id + n + 1, [](int x, int y) { return dep[x] < dep[y]; });

  for (i = 2; i <= n; ++i) {
    dfs(1);
    solve(1, id[i]);
  }

  printf("!");
  for (i = 2; i <= n; ++i) printf(" %d", fa[i]);
  printf("\n");
  fflush(stdout);

  return 0;
}

Phân tích chuỗi dài

Phân tích chuỗi dài là một biến thể khác của phân tích chuỗi.

  • Con nặng là con có cây con sâu nhất. Nếu có nhiều con sâu nhất, chọn một. Nếu không có con, không có con nặng.
  • Con nhẹ là các con còn lại.
  • Cạnh nối tới con nặng gọi là cạnh nặng.
  • Cạnh nối tới con nhẹ gọi là cạnh nhẹ.
  • Nhiều cạnh nặng nối tiếp tạo thành chuỗi nặng.
  • Đỉnh lẻ cũng coi là chuỗi nặng, nên toàn bộ cây được chia thành nhiều chuỗi nặng.

Minh họa (cách chia này cũng là phân tích chuỗi nặng hoặc chuỗi dài):

HLD

Cách cài đặt giống phân tích chuỗi nặng, không trình bày lại.

Ứng dụng phổ biến

Phân tích chuỗi dài đảm bảo số lần chuyển chuỗi khi đi từ một đỉnh tới gốc là \(O(\sqrt{n})\).

Làm sao kiểm tra số lần chuyển chuỗi đạt tối đa?

Có thể xây cây nhị phân như sau:

Gọi tham số cây là \(D\).

Nếu \(D \neq 0\), xây cây nhị phân trái với tham số \(D-1\), cây phải là chuỗi dài \(2D-1\).

Nếu \(D = 0\), xây một lá riêng và kết thúc.

Như vậy, các lá sẽ có đường đi tới gốc toàn cạnh nhẹ, số đỉnh \(D^2\).

Chọn \(D=\sqrt{n}\) là đạt tối đa.

Tối ưu DP bằng phân tích chuỗi dài

Các bài DP trên cây có một chiều là độ sâu có thể tối ưu bằng phân tích chuỗi dài.

Ý tưởng: mỗi đỉnh kế thừa trạng thái DP của con nặng, các con nhẹ thì hợp trạng thái vào.

Codeforces 1009 F. Dominant Indices

Cho cây \(n\) đỉnh gốc \(1\).

Định nghĩa mảng độ sâu của đỉnh \(x\) là \([d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]\), với \(d_{x, i}\) là số đỉnh \(y\) thỏa:

  • \(x\) là tổ tiên của \(y\);
  • Đường đi từ \(x\) tới \(y\) có đúng \(i\) cạnh.

Chỉ số chủ đạo của \(x\) là chỉ số \(j\) thỏa:

  • Với mọi \(k < j\), \(d_{x, k} < d_{x, j}\);
  • Với mọi \(k > j\), \(d_{x, k} \le d_{x, j}\).

Tính chỉ số chủ đạo cho mọi đỉnh.

Giải thích

Gọi \(f_{i,j}\) là số đỉnh trong cây con \(i\) cách \(i\) đúng \(j\) cạnh.

Nếu chuyển trạng thái brute-force thì \(O(n^2)\).

Ý tưởng: mỗi lần chuyển trạng thái, kế thừa mảng DP của con nặng và đáp án, sau đó cập nhật.

Đầu tiên, thêm 1 vào đầu mảng DP của con nặng (đỉnh hiện tại).

Sau đó, hợp mảng DP của các con nhẹ vào mảng hiện tại.

Vì mảng DP của con nhẹ có độ dài bằng chuỗi nặng của nó, tổng độ dài các chuỗi nặng là \(n\).

Do đó, hợp mảng DP của các con nhẹ tổng \(O(n)\).

Mã tham khảo 
 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
#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 1000005;

struct edge {
  int to, next;
} e[N * 2];

int head[N], tot, n;
int d[N], fa[N], mx[N];
int *f[N], g[N], mxp[N];
int dfn[N];

void add(int x, int y) {
  e[++tot] = edge{y, head[x]};
  head[x] = tot;
}

void dfs1(int x) {  // 第一次插入一个1
  d[x] = 1;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x]) {
      fa[e[i].to] = x;
      dfs1(e[i].to);
      d[x] = max(d[x], d[e[i].to] + 1);
      if (d[e[i].to] > d[mx[x]]) mx[x] = e[i].to;
    }
}

void dfs2(int x) {  // 第二次合并
  dfn[x] = ++*dfn;
  f[x] = g + dfn[x];
  if (mx[x]) dfs2(mx[x]);
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x] && e[i].to != mx[x]) dfs2(e[i].to);
}

void getans(int x) {  // 暴力合并算答案
  if (mx[x]) {
    getans(mx[x]);
    mxp[x] = mxp[mx[x]] + 1;
  }
  f[x][0] = 1;
  if (f[x][mxp[x]] <= 1) mxp[x] = 0;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x] && e[i].to != mx[x]) {
      getans(e[i].to);
      int len = d[e[i].to];
      for (int j = 0; j <= len - 1; j++) {
        f[x][j + 1] += f[e[i].to][j];
        if (f[x][j + 1] > f[x][mxp[x]]) mxp[x] = j + 1;
        if (f[x][j + 1] == f[x][mxp[x]] && j + 1 < mxp[x]) mxp[x] = j + 1;
      }
    }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dfs1(1);
  dfs2(1);
  getans(1);
  for (int i = 1; i <= n; i++) cout << mxp[i] << '\n';
}

Lưu ý: thường mảng DP được cấp phát cho cả chuỗi nặng, mỗi đỉnh có con trỏ đầu riêng.

Độ dài mảng DP có thể xác định theo độ sâu lớn nhất của cây con.

Kỹ thuật tối ưu DP bằng phân tích chuỗi dài còn nhiều biến thể, như đánh dấu,... không trình bày thêm.

Tham khảo blog của zhoushuyu.

Truy vấn tổ tiên cấp k

Tức là hỏi một đỉnh nhảy lên cha \(k\) lần thì tới đâu.

Giả sử đã tiền xử lý tổ tiên \(2^i\) cho mỗi đỉnh.

Giả sử tìm được tổ tiên \(2^i\) của đỉnh truy vấn, với \(2^i \le k < 2^{i+1}\).

Tìm vị trí trên chuỗi nặng theo độ sâu. Gọi độ dài chuỗi là \(d\).

Tiền xử lý cho mỗi chuỗi nặng, lưu tổ tiên từ \(1\) tới \(d\) cho gốc chuỗi.

Theo tính chất phân tích chuỗi dài, \(k-2^i \le 2^i \leq d\), nên có thể \(O(1)\) truy vấn tổ tiên cấp \(k\) trên chuỗi.

Tiền xử lý cần truy vấn tổ tiên \(2^i\), và lưu bảng cho mỗi chuỗi nặng.

Tiền xử lý \(O(n\log n)\), truy vấn \(O(1)\).

Bài tập

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:GoodCoder666, Ir1d, Marcythm, ouuan, hsfzLZH1, Xeonacid, greyqz, Chrogeek, ftxj, sshwy, LuoshuiTianyi, hyp1231, sun2snow
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply