Bỏ qua

Phân tách cây động

Phân hoạch động trên cây (Dynamic Centroid Decomposition)

Phân hoạch động trên cây dùng để giải các bài toán thống kê thông tin đường đi trên cây khi có thay đổi trọng số đỉnh/cạnh.

Cây phân hoạch (Centroid Tree)

Nhắc lại quá trình phân hoạch trên cây.

Với một đỉnh \(x\), các đường đi đơn giản trong cây con của \(x\) gồm hai loại: các đường đi qua \(x\) (gồm một hoặc hai đường đi xuất phát từ \(x\)), và các đường đi không qua \(x\) (đã nằm trong các cây con của các con của \(x\)).

Để tính thông tin các đường đi trong cây con, ta chọn một điểm phân hoạch (centroid) \(rt\), tính thông tin các đường đi qua \(rt\), sau đó với mỗi con của \(rt\), loại bỏ \(rt\) và tiếp tục phân hoạch trên phần còn lại. Các centroid được chọn tạo thành một cây gọi là cây phân hoạch. Tổng kích thước các khối liên thông ở cùng một tầng của cây phân hoạch là \(O(n)\), nên độ phức tạp phụ thuộc vào độ sâu cây phân hoạch \(h\), tổng là \(O(nh)\).

Có thể chứng minh rằng nếu luôn chọn trọng tâm (centroid) của khối liên thông làm điểm phân hoạch, độ sâu cây phân hoạch là nhỏ nhất, \(O(\log n)\). Như vậy, ta có thể thống kê thông tin \(O(n^2)\) đường đi trên cây trong \(O(n\log n)\) thời gian.

Vì cấu trúc cây không thay đổi trong quá trình phân hoạch động, nên hình dạng cây phân hoạch cũng không thay đổi.

Tham khảo mã xây dựng cây phân hoạch:

 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
void calcsiz(int x, int f) {
  siz[x] = 1;
  maxx[x] = 0;
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != f && !vis[p[j]]) {
      calcsiz(p[j], x);
      siz[x] += siz[p[j]];
      maxx[x] = max(maxx[x], siz[p[j]]);
    }
  maxx[x] =
      max(maxx[x], sum - siz[x]);  // maxx[x] là kích thước cây con lớn nhất khi lấy x làm gốc
  if (maxx[x] < maxx[rt])
    rt = x;  // Không dùng <= để đảm bảo rt không đổi ở lần calcsiz thứ hai
}

void pre(int x) {
  vis[x] = true;  // Đánh dấu không xét lại x ở các bước sau
  for (int j = h[x]; j; j = nxt[j])
    if (!vis[p[j]]) {
      sum = siz[p[j]];
      rt = 0;
      maxx[rt] = inf;
      calcsiz(p[j], -1);
      calcsiz(rt, -1);  // Tính lại để lấy kích thước các cây con khi rt làm gốc
      fa[rt] = x;
      pre(rt);  // Ghi nhận cha trên cây phân hoạch
    }
}

int main() {
  sum = n;
  rt = 0;
  maxx[rt] = inf;
  calcsiz(1, -1);
  calcsiz(rt, -1);
  pre(rt);
}

Cách thực hiện cập nhật

Khi truy vấn hoặc cập nhật, ta sẽ duyệt lên các cha trên cây phân hoạch. Vì độ sâu cây phân hoạch tối đa \(O(\log n)\) nên độ phức tạp được đảm bảo.

Trong quá trình phân hoạch động, cần biết khoảng cách từ một đỉnh tới các tổ tiên trên cây phân hoạch. Vì mỗi đỉnh có tối đa \(O(\log n)\) tổ tiên, ta có thể tiền xử lý độ sâu \(dep[x]\) hoặc dùng LCA để tính khoảng cách. Lưu ý: Khoảng cách từ một đỉnh tới các tổ tiên trên cây phân hoạch không nhất thiết tăng dần, không thể cộng dồn!

Một đỉnh có thể bị tính lặp trong thông tin của các tổ tiên trên cây phân hoạch, cần loại bỏ phần trùng lặp. Thường sẽ lưu hai loại thông tin cho mỗi khối liên thông: một là thông tin khoảng cách tới centroid, hai là thông tin khoảng cách tới cha centroid trên cây phân hoạch. Phần này sẽ được trình bày trong ví dụ.

Ví dụ 「ZJOI2007」Trốn tìm

Cho cây \(n\) đỉnh, ban đầu mọi đỉnh đều màu đen. Thực hiện hai thao tác:

  1. Đảo màu một đỉnh (đen thành trắng, trắng thành đen);

  2. Hỏi khoảng cách lớn nhất giữa hai đỉnh đen trên cây.

    \(n\le 10^5,m\le 5\times 10^5\)

Xây cây phân hoạch, với mỗi đỉnh \(x\) lưu hai heap có thể xóa. \(dist[x]\) lưu khoảng cách từ các đỉnh đen trong khối liên thông của \(x\) tới \(x\), \(ch[x]\) lưu khoảng cách từ các đỉnh đen trong khối liên thông của \(x\) và các con trên cây phân hoạch tới \(x\). Vì khi tìm đường đi dài nhất, hai đầu không được nằm trong cùng một cây con, nên chỉ lưu giá trị của chính nó và giá trị lớn nhất từ mỗi cây con. Tổng lớn nhất hai giá trị trong \(ch[x]\) là đường đi dài nhất qua centroid \(x\). Dùng heap \(ans\) lưu đáp án của mọi centroid, giá trị lớn nhất là đáp án cần tìm.

Khi \(dist[x]\) thay đổi, có thể cập nhật \(ch[x],ans\) trong \(O(\log n)\).

Khi đảo màu một đỉnh \(x\), nếu ban đầu là đen thì xóa, nếu là trắng thì thêm. Với mọi tổ tiên \(u\) của \(x\), thêm/xóa \(dist(x,u)\) vào \(dist[u]\), đồng thời cập nhật \(ch[x],ans\). Đặc biệt, thêm/xóa giá trị \(0\) vào \(ch[x]\).

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int MAXN = 100010;
constexpr int inf = 2e9;
int n, a, b, m, x, col[MAXN];
// 0 off 1 on
char op;
int cur, h[MAXN * 2], nxt[MAXN * 2], p[MAXN * 2];

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

bool vis[MAXN];
int rt, sum, siz[MAXN], maxx[MAXN], fa[MAXN], dep[MAXN];

void calcsiz(int x, int f) {
  siz[x] = 1;
  maxx[x] = 0;
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != f && !vis[p[j]]) {
      calcsiz(p[j], x);
      siz[x] += siz[p[j]];
      maxx[x] = max(maxx[x], siz[p[j]]);
    }
  maxx[x] =
      max(maxx[x], sum - siz[x]);  // maxx[x] 表示以 x 为根时的最大子树大小
  if (maxx[x] < maxx[rt])
    rt = x;  // 这里不能写 <= ，保证在第二次 calcsiz 时 rt 不改变
}

struct heap {
  priority_queue<int> A, B;  // heap=A-B

  void insert(int x) { A.push(x); }

  void erase(int x) { B.push(x); }

  int top() {
    while (!B.empty() && A.top() == B.top()) A.pop(), B.pop();
    return A.top();
  }

  void pop() {
    while (!B.empty() && A.top() == B.top()) A.pop(), B.pop();
    A.pop();
  }

  int top2() {
    int t = top(), ret;
    pop();
    ret = top();
    A.push(t);
    return ret;
  }

  int size() { return A.size() - B.size(); }
} dist[MAXN], ch[MAXN], ans;

void dfs(int x, int f, int d, heap& y) {
  y.insert(d);
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != f && !vis[p[j]]) dfs(p[j], x, d + 1, y);
}

void pre(int x) {
  vis[x] = true;  // 不考虑 x
  for (int j = h[x]; j; j = nxt[j])
    if (!vis[p[j]]) {
      rt = 0;
      maxx[rt] = inf;
      sum = siz[p[j]];
      calcsiz(p[j], -1);
      calcsiz(rt, -1);  // 计算两次，第二次求出以 rt 为根时的各子树大小
      fa[rt] = x;
      dfs(p[j], -1, 1, dist[rt]);
      ch[x].insert(dist[rt].top());
      dep[rt] = dep[x] + 1;
      pre(rt);  // 记录点分树上的父亲
    }
  ch[x].insert(0);
  if (ch[x].size() >= 2)
    ans.insert(ch[x].top() + ch[x].top2());
  else if (ch[x].size())
    ans.insert(ch[x].top());
}

struct LCA {
  int dep[MAXN], lg[MAXN], fa[MAXN][20];

  void dfs(int x, int f) {
    for (int j = h[x]; j; j = nxt[j])
      if (p[j] != f) dep[p[j]] = dep[x] + 1, fa[p[j]][0] = x, dfs(p[j], x);
  }

  void init() {
    dfs(1, -1);
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (int j = 1; j <= lg[n]; j++)
      for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
  }

  int query(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    int k = dep[y] - dep[x];
    for (int i = 0; k; k = k / 2, i++)
      if (k & 1) y = fa[y][i];
    if (x == y) return x;
    k = dep[x];
    for (int i = lg[k]; i >= 0; i--)
      if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
  }

  int dist(int x, int y) { return dep[x] + dep[y] - 2 * dep[query(x, y)]; }
} lca;

int d[MAXN][20];

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);
  lca.init();
  rt = 0;
  maxx[rt] = inf;
  sum = n;
  calcsiz(1, -1);
  calcsiz(rt, -1);
  pre(rt);
  for (int i = 1; i <= n; i++)
    for (int j = i; j; j = fa[j]) d[i][dep[i] - dep[j]] = lca.dist(i, j);
  cin >> m;
  while (m--) {
    cin >> op;
    if (op == 'G') {
      if (ans.size())
        cout << ans.top() << '\n';
      else
        cout << "-1\n";
    } else {
      cin >> x;
      if (!col[x]) {
        if (ch[x].size() >= 2) ans.erase(ch[x].top() + ch[x].top2());
        ch[x].erase(0);
        if (ch[x].size() >= 2) ans.insert(ch[x].top() + ch[x].top2());
        for (int i = x; fa[i]; i = fa[i]) {
          if (ch[fa[i]].size() >= 2)
            ans.erase(ch[fa[i]].top() + ch[fa[i]].top2());
          ch[fa[i]].erase(dist[i].top());
          dist[i].erase(d[x][dep[x] - dep[fa[i]]]);
          if (dist[i].size()) ch[fa[i]].insert(dist[i].top());
          if (ch[fa[i]].size() >= 2)
            ans.insert(ch[fa[i]].top() + ch[fa[i]].top2());
        }
      } else {
        if (ch[x].size() >= 2) ans.erase(ch[x].top() + ch[x].top2());
        ch[x].insert(0);
        if (ch[x].size() >= 2) ans.insert(ch[x].top() + ch[x].top2());
        for (int i = x; fa[i]; i = fa[i]) {
          if (ch[fa[i]].size() >= 2)
            ans.erase(ch[fa[i]].top() + ch[fa[i]].top2());
          if (dist[i].size()) ch[fa[i]].erase(dist[i].top());
          dist[i].insert(d[x][dep[x] - dep[fa[i]]]);
          ch[fa[i]].insert(dist[i].top());
          if (ch[fa[i]].size() >= 2)
            ans.insert(ch[fa[i]].top() + ch[fa[i]].top2());
        }
      }
      col[x] ^= 1;
    }
  }
  return 0;
}

Ví dụ Luogu P6329【Mẫu】Cây phân hoạch | Sóng chấn động

Cho cây \(n\) đỉnh, mỗi đỉnh có trọng số \(v[x]\). Thực hiện hai thao tác:

  1. Hỏi tổng trọng số các đỉnh cách \(x\) không quá \(y\);
  2. Đổi trọng số đỉnh \(x\) thành \(y\), tức \(v[x]=y\).

Dùng segment tree động lưu thông tin trọng số theo khoảng cách.

Tương tự ví dụ trên, với mỗi centroid \(x\) lưu segment tree \(dist[x]\) (lưu tổng trọng số các đỉnh trong khối liên thông của \(x\) theo khoảng cách tới \(x\)), và segment tree \(ch[x]\) (lưu tổng trọng số các đỉnh trong khối liên thông của \(x\) theo khoảng cách tới cha centroid trên cây phân hoạch).

Khi truy vấn hoặc cập nhật, cần duyệt lên các tổ tiên trên cây phân hoạch.

Ví dụ truy vấn: hỏi tổng trọng số các đỉnh cách \(x\) không quá \(y\), cộng tổng từ \(dist[x]\) với khoảng cách \(0\) đến \(y\), sau đó với mỗi tổ tiên \(u\) của \(x\), gọi \(v\) là tổ tiên thấp hơn, \(d=dist(x,u)\), cộng tổng từ \(dist[u]\) với khoảng cách \(0\) đến \(y-d\), rồi trừ đi tổng từ \(ch[v]\) với khoảng cách \(0\) đến \(y-d\) (loại bỏ phần trùng).

Khi cập nhật, cần cập nhật cả \(dist[x]\) và \(ch[x]\).

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
157
158
159
160
161
162
163
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 100010;
constexpr int inf = 2e9;
constexpr int ddd = 6000010;

struct Segtree {
  int cnt, rt[MAXN], sum[ddd], lc[ddd], rc[ddd];

  void update(int& o, int l, int r, int x, int v) {
    if (!o) o = ++cnt;
    if (l == r) {
      sum[o] += v;
      return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
      update(lc[o], l, mid, x, v);
    else
      update(rc[o], mid + 1, r, x, v);
    sum[o] = sum[lc[o]] + sum[rc[o]];
  }

  int query(int o, int l, int r, int ql, int qr) {
    if (!o || r < ql || l > qr) return 0;
    if (ql <= l && r <= qr) return sum[o];
    int mid = (l + r) >> 1;
    return query(lc[o], l, mid, ql, qr) + query(rc[o], mid + 1, r, ql, qr);
  }
} dist, ch;

int n, m, val[MAXN], u, v, op, x, y, lstans;
int cur, h[MAXN * 2], nxt[MAXN * 2], p[MAXN * 2];

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

struct LCA {
  int dep[MAXN], lg[MAXN], fa[MAXN][20];

  void dfs(int x, int f) {
    for (int j = h[x]; j; j = nxt[j])
      if (p[j] != f) dep[p[j]] = dep[x] + 1, fa[p[j]][0] = x, dfs(p[j], x);
  }

  void init() {
    dep[1] = 1;
    dfs(1, -1);
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (int j = 1; j <= lg[n]; j++)
      for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
  }

  int query(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    int k = dep[y] - dep[x];
    for (int i = 0; k; k = k / 2, i++)
      if (k & 1) y = fa[y][i];
    if (x == y) return x;
    k = dep[x];
    for (int i = lg[k]; i >= 0; i--)
      if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
  }

  int dist(int x, int y) { return dep[x] + dep[y] - 2 * dep[query(x, y)]; }
} lca;

int rt, sum, siz[MAXN], maxx[MAXN], fa[MAXN];
int d[MAXN][20], dep[MAXN];
bool vis[MAXN];

void calcsiz(int x, int fa) {
  siz[x] = 1;
  maxx[x] = 0;
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) {
      calcsiz(p[j], x);
      siz[x] += siz[p[j]];
      maxx[x] = max(maxx[x], siz[p[j]]);
    }
  maxx[x] =
      max(maxx[x], sum - siz[x]);  // maxx[x] 表示以 x 为根时的最大子树大小
  if (maxx[x] < maxx[rt])
    rt = x;  // 这里不能写 <= ，保证在第二次 calcsiz 时 rt 不改变
}

void dfs1(int x, int fa, int y, int d) {
  ch.update(ch.rt[y], 0, n, d, val[x]);
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) dfs1(p[j], x, y, d + 1);
}

void dfs2(int x, int fa, int y, int d) {
  dist.update(dist.rt[y], 0, n, d, val[x]);
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) dfs2(p[j], x, y, d + 1);
}

void pre(int x) {
  vis[x] = true;  // 表示在之后的过程中不考虑 x 这个点
  dfs2(x, -1, x, 0);
  for (int j = h[x]; j; j = nxt[j])
    if (!vis[p[j]]) {
      rt = 0;
      maxx[rt] = inf;
      sum = siz[p[j]];
      calcsiz(p[j], -1);
      calcsiz(rt, -1);  // 计算两次，第二次求出以 rt 为根时的各子树大小
      dfs1(p[j], -1, rt, 1);
      fa[rt] = x;
      dep[rt] = dep[x] + 1;
      pre(rt);  // 记录点分树上的父亲
    }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> val[i];
  for (int i = 1; i < n; i++) cin >> u >> v, add_edge(u, v), add_edge(v, u);
  lca.init();
  rt = 0;
  maxx[rt] = inf;
  sum = n;
  calcsiz(1, -1);
  calcsiz(rt, -1);
  pre(rt);
  for (int i = 1; i <= n; i++)
    for (int j = i; j; j = fa[j]) d[i][dep[i] - dep[j]] = lca.dist(i, j);
  while (m--) {
    cin >> op >> x >> y;
    x ^= lstans;
    y ^= lstans;
    if (op == 0) {
      lstans = dist.query(dist.rt[x], 0, n, 0, y);
      int nww = 0;
      for (int i = x; fa[i]; i = fa[i]) {
        nww = d[x][dep[x] - dep[fa[i]]];  // lca.dist(x,fa[i]);
        lstans += dist.query(dist.rt[fa[i]], 0, n, 0, y - nww);
        lstans -= ch.query(ch.rt[i], 0, n, 0, y - nww);
      }
      cout << lstans << '\n';
    }
    if (op == 1) {
      int nww = 0;
      dist.update(dist.rt[x], 0, n, 0, y - val[x]);
      for (int i = x; fa[i]; i = fa[i]) {
        nww = d[x][dep[x] - dep[fa[i]]];  // lca.dist(x,fa[i]);
        dist.update(dist.rt[fa[i]], 0, n, nww, y - val[x]);
        ch.update(ch.rt[i], 0, n, nww, y - val[x]);
      }
      val[x] = y;
    }
  }
  return 0;
}

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply