Bỏ qua

Euler Tour Tree

tác giả: Backl1ght

Euler Tour Tree (Cây Du lịch Euler, Cây Chu trình Euler, sau đây gọi tắt là ETT) là một cấu trúc dữ liệu có thể giải quyết các bài toán cây động (dynamic tree). ETT chuyển các thao tác của cây động thành các thao tác trên đoạn của dãy thứ tự DFS của nó, sau đó dùng các cấu trúc dữ liệu khác để duy trì các thao tác trên đoạn của dãy, từ đó duy trì các thao tác của cây động. Ví dụ, ETT chuyển thao tác thêm cạnh của cây động thành nhiều thao tác tách dãy và hợp dãy, nếu có thể duy trì các thao tác tách dãy và hợp dãy, có thể duy trì thao tác thêm cạnh của cây động.

LCT (Link/Cut Tree) cũng là một cấu trúc dữ liệu có thể giải quyết các bài toán cây động, so với ETT thì LCT phổ biến hơn. LCT thực sự thích hợp hơn để duy trì thông tin trên đường đi (path), trong khi ETT thích hợp hơn để duy trì thông tin cây con (subtree). Ví dụ, ETT có thể duy trì giá trị nhỏ nhất trên cây con mà LCT không thể.

ETT có thể sử dụng bất kỳ cấu trúc dữ liệu nào để duy trì, chỉ cần cấu trúc dữ liệu đó hỗ trợ các thao tác trên đoạn dãy tương ứng, và thỏa mãn yêu cầu về độ phức tạp. Thông thường sẽ sử dụng các cây tìm kiếm nhị phân cân bằng như Splay, Treap để duy trì các thao tác trên đoạn, mà các cấu trúc dữ liệu này duy trì các thao tác trên đoạn với độ phức tạp đều là \(O(\log n)\), từ đó có thể duy trì các thao tác cây động trong thời gian \(O(\log n)\). Nếu sử dụng cây tìm kiếm cân bằng đa ngôi (multiway balanced search tree) ví dụ như B-tree để duy trì các thao tác trên đoạn, cũng có thể đạt được độ phức tạp tốt hơn.

Thực ra ETT có thể được hiểu là một tư tưởng, đó là thông qua việc duy trì một dãy nào đó tương ứng một-một với cây gốc, từ đó đạt được mục đích duy trì cây gốc. Bài viết này chỉ giới thiệu một số cách triển khai và ứng dụng khả thi của tư tưởng này.

Biểu diễn Chu trình Euler của cây

Nếu coi một cạnh của cây là hai cạnh có hướng, thì có thể biểu diễn cây thành một chu trình Euler của đồ thị có hướng, gọi là Biểu diễn Chu trình Euler của cây (Euler tour representation, ETR).

Dãy cần duy trì sau này thực chất là một biến thể của ETR, coi các nút trong cây như là vòng lặp tự thân cũng được thêm vào ETR, nhưng do tác giả trong bài báo gốc không đặt tên mới cho nó, nên vẫn gọi nó là ETR.

Có thể thu được Biểu diễn Chu trình Euler của cây \(T\) thông qua thuật toán sau:

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{Một cây có gốc }T\\ 2 & \textbf{Output. } \text{Dãy DFS của cây có gốc }T\\ 3 & \operatorname{ET}(u)\\ 4 & \qquad \text{thăm đỉnh }u\\ 5 & \qquad \text{cho tất cả con } v \text{ của } u\\ 6 & \qquad \qquad \text{thăm cạnh có hướng } u \to v\\ 7 & \qquad \qquad \operatorname{ET}(v)\\ 8 & \qquad \qquad \text{thăm cạnh có hướng } v \to u\\ \end{array} \]

Biểu diễn Chu trình Euler \(\operatorname{ETR}(T)\) của cây \(T\) ban đầu là rỗng. Trong quá trình DFS, mỗi lần thăm một nút hoặc một cạnh có hướng thì thêm nó vào cuối \(\operatorname{ETR}(T)\), như vậy có thể thu được \(\operatorname{ETR}(T)\).

Nếu \(T\) chứa \(n\) nút, thì chứa \(2n - 2\) cạnh có hướng, mà trong quá trình DFS, mỗi nút và mỗi cạnh có hướng đều được thăm một lần, nên độ dài của \(\operatorname{ETR}(T)\) là \(3n - 2\).

Coi nút \(u\) như một vòng lặp tự thân, khi đó \(\operatorname{ETR}(T)\) có thể coi là một chu trình Euler trong đồ thị có hướng. Có thể cắt tại một điểm nào đó trong chu trình Euler, biến nó thành một chuỗi các cạnh nối đầu cuối với nhau; cũng có thể dán lại chỗ bị cắt để biến chuỗi này trở lại thành chu trình Euler; cũng có thể thông qua việc thêm một số cạnh để ghép hai chuỗi như vậy thành một chu trình Euler mới.

Trong phần sau, nếu không nói rõ, dãy được duy trì mặc định là biểu diễn chu trình Euler của cây.

Các thao tác cơ bản của ETT

3 thao tác sau được coi là các thao tác cơ bản của ETT, đều có thể được chuyển đổi thành số lần thao tác trên dãy là hằng số, vì vậy độ phức tạp của 3 thao tác này cùng bậc với thao tác trên dãy.

Ở đây chỉ đưa ra một cách triển khai khả thi, chỉ cần có thể ghép dãy tương ứng với thao tác sau khi sửa đổi bằng số lần thao tác trên dãy là hằng số là được.

MakeRoot(u)

Tức là thao tác đổi gốc. Thao tác đổi gốc trong ETT được chuyển đổi thành 1 thao tác tách dãy và 1 thao tác hợp dãy, cũng có thể hiểu là 1 thao tác dịch chuyển đoạn.

Ký hiệu cây chứa nút \(u\) là \(T\), gốc hiện tại là \(r\), bây giờ muốn đổi gốc thành \(u\). Dãy tương ứng với cây \(T\) là \(L\), tách \(L\) tại \((u, u)\) thành dãy \(L^1\) và \(L^2\), phần trước chứa các phần tử trước \((u, u)\) trong \(L\) và \((u, u)\), phần sau chứa các phần tử còn lại. Dãy thu được bằng cách hợp nhất lần lượt \(L^2\) và \(L^1\) là dãy tương ứng với cây sau khi đổi gốc.

Ở đây có thể hiểu là thao tác xoay chu trình Euler. Chu trình Euler là một vòng tròn, việc xoay không làm thay đổi cấu trúc của chu trình Euler, tức là không làm thay đổi cấu trúc cây, chỉ là đưa nút \(u\) xoay đến vị trí gốc.

Insert(u, v)

Tức là thao tác thêm cạnh. Thao tác thêm cạnh trong ETT được chuyển đổi thành 2 thao tác tách dãy và 5 thao tác hợp dãy.

Ký hiệu cây chứa nút \(u\) là \(T_1\), cây chứa nút \(v\) là \(T_2\), sau khi thêm cạnh hai cây hợp nhất thành một cây \(T\). Dãy tương ứng với cây \(T_1\) là \(L_1\), dãy tương ứng với cây \(T_2\) là \(L_2\).

Tách \(L_1\) tại \((u, u)\) thành dãy \(L_1^1\) và \(L_1^2\), phần trước chứa các phần tử trước \((u, u)\) trong \(L_1\) và \((u, u)\), phần sau chứa các phần tử còn lại. Tương tự, tách \(L_2\) tại \((v, v)\) thành dãy \(L_2^1\) và \(L_2^2\). Dãy tương ứng với cây \(T\) là \(L\) thu được bằng cách hợp nhất lần lượt \(L_1^2, L_1^1, [(u, v)], L_2^2, L_2^1, [(v, u)]\).

Ở đây có thể hiểu là hai thao tác đổi gốc, sau đó ngắt hai chu trình Euler tại vị trí gốc hiện tại, rồi dùng hai cạnh có hướng mới để ghép hai chu trình Euler thành một chu trình Euler mới.

Delete(u, v)

Tức là thao tác xóa cạnh. Thao tác xóa cạnh trong ETT được chuyển đổi thành 4 thao tác tách dãy và 1 thao tác hợp dãy.

Ký hiệu cây chứa cạnh \((u, v)\) và cạnh \((v, u)\) là \(T\), dãy tương ứng là \(L\). Sau khi xóa cạnh, \(T\) được chia thành hai cây.

Tách \(L\) thành \(L_1, [(u, v)], L_2, [(v, u)], L_3\). Dãy tương ứng với hai cây tạo thành sau khi xóa cạnh lần lượt là \(L_2\) và \(L_1, L_3\). Chú ý, trong dãy \(L\), \([(u, v)]\) có thể xuất hiện sau \([(v, u)]\), khi đó có thể đổi giá trị \(u\) và \(v\) rồi mới thao tác.

Ở đây có thể hiểu là cắt một chu trình Euler tại hai cạnh có hướng để tạo thành hai chuỗi, sau đó hai chuỗi tự nối đầu cuối để tạo thành hai chu trình Euler mới.

Triển khai

Dưới đây lấy Treap không xoay (non-splay Treap) làm ví dụ để giới thiệu cách triển khai ETT, đòi hỏi người đọc cần biết trước về nội dung liên quan đến thao tác trên đoạn của cây tìm kiếm nhị phân không xoay.

Split và Merge đều là các thao tác cơ bản của Treap không xoay, ở đây không nhắc lại.

SplitUp2(u)

Giả sử dãy mà \(u\) thuộc về là \(L\), tách \(L\) tại \(u\) thành dãy \(L^1\) và \(L^2\), phần trước chứa các phần tử trước \((u, u)\) trong \(L\) và \((u, u)\), phần sau chứa các phần tử còn lại.

Nếu mỗi nút trong Treap còn duy trì cha của nó, thì có thể thực hiện tính toán vị trí của phần tử tương ứng với nút Treap trong dãy trong thời gian \(O(\log n)\), sau đó dựa vào vị trí để Split có thể thực hiện chức năng trên.

Cũng có thể tách từ dưới lên để thực hiện chức năng trên, cách này so với phương pháp trên sẽ hiệu quả hơn. Cụ thể là, trong quá trình nhảy từ nút \(u\) lên gốc, dựa vào tính chất của cây tìm kiếm nhị phân có thể xác định mỗi nút trong \(L\) nằm trước hay sau \(u\), dựa vào điều này có thể tính toán vị trí của \(u\) trong dãy, cũng có thể xác định mỗi nút thuộc về cây nào trong các cây sau khi tá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
38
39
40
41
42
43
/*
 * Bottom up split treap p into 2 treaps a and b.
 *   - a: a treap containing nodes with position less than or equal to p.
 *   - b: a treap containing nodes with postion greater than p.
 *
 * In the other word, split sequence containning p into two sequences, the first
 * one contains elements before p and element p, the second one contains
 * elements after p.
 */
static std::pair<Node*, Node*> SplitUp2(Node* p) {
  Node *a = nullptr, *b = nullptr;
  b = p->right_;
  if (b) b->parent_ = nullptr;
  p->right_ = nullptr;

  bool is_p_left_child_of_parent = false;
  bool is_from_left_child = false;
  while (p) {
    Node* parent = p->parent_;

    if (parent) {
      is_p_left_child_of_parent = (parent->left_ == p);
      if (is_p_left_child_of_parent) {
        parent->left_ = nullptr;
      } else {
        parent->right_ = nullptr;
      }
      p->parent_ = nullptr;
    }

    if (!is_from_left_child) {
      a = Merge(p, a);
    } else {
      b = Merge(b, p);
    }

    is_from_left_child = is_p_left_child_of_parent;
    p->Maintain();
    p = parent;
  }

  return {a, b};
}

SplitUp3(u)

Giả sử dãy mà \(u\) thuộc về là \(L\), tách \(L\) tại \(u\) thành dãy \(L^1, u\) và \(L^2\), phần trước chứa các phần tử trước \(u\) trong \(L\), phần sau chứa các phần tử còn lại.

Có thể thực hiện chức năng trên bằng cách sửa đổi một chút dựa trên SplitUp2.

MakeRoot(u)

Dễ dàng thu được dựa trên SplitUp2 và Merge.

1
2
3
4
5
void MakeRoot(int u) {
  Node* vertex_u = vertices_[u];
  auto [L1, L2] = Treap::SplitUp2(vertex_u);
  Treap::Merge(L2, L1);
}

Insert(u, v)

Dễ dàng thu được dựa trên SplitUp2 và Merge.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void Insert(int u, int v) {
  Node* vertex_u = vertices_[u];
  Node* vertex_v = vertices_[v];

  Node* edge_uv = AllocateNode(u, v);
  Node* edge_vu = AllocateNode(v, u);
  tree_edges_[u][v] = edge_uv;
  tree_edges_[v][u] = edge_vu;

  auto [L11, L12] = Treap::SplitUp2(vertex_u);
  auto [L21, L22] = Treap::SplitUp2(vertex_v);

  Node* L = L12;
  L = Treap::Merge(L, L11);
  L = Treap::Merge(L, edge_uv);
  L = Treap::Merge(L, L22);
  L = Treap::Merge(L, L21);
  L = Treap::Merge(L, edge_vu);
}

Delete(u, v)

Dễ dàng thu được dựa trên SplitUp3 và Merge.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void Delete(int u, int v) {
  Node* edge_uv = tree_edges_[u][v];
  Node* edge_vu = tree_edges_[v][u];
  tree_edges_[u].erase(v);
  tree_edges_[v].erase(u);

  int position_uv = Treap::GetPosition(edge_uv);
  int position_vu = Treap::GetPosition(edge_vu);
  if (position_uv > position_vu) {
    std::swap(edge_uv, edge_vu);
    std::swap(position_uv, position_vu);
  }

  auto [L1, uv, _] = Treap::SplitUp3(edge_uv);
  auto [L2, vu, L3] = Treap::SplitUp3(edge_vu);
  Treap::Merge(L1, L3);

  FreeNode(edge_uv);
  FreeNode(edge_vu);
}

Duy trì tính liên thông

Hai điểm \(u\) và \(v\) liên thông khi và chỉ khi hai điểm thuộc cùng một cây \(T\), tức là \((u, u)\) và \((v, v)\) thuộc \(\operatorname{ETR}(T)\), điều này có thể được phán đoán bằng cách kiểm tra xem nút Treap tương ứng với nút \(u\) và nút \(v\) có nằm trong cùng một Treap (có cùng nút gốc) hay không.

Bài toán ví dụ P2147 [SDOI2008] Khảo sát hang động

Bài toán mẫu kiểm tra tính liên thông.

Mã nguồn 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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <random>
#include <sstream>

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve_case(t);
  }
  return 0;
}

/**
 * Dynamic Forest Maintained With Euler Tour Tree.
 *
 * As said in reference, link and cut operation of dynamic trees can be
 * transformed into sequence split and sequence merge operation, which can be
 * easily maintained using balanced search trees like Treap.
 *
 * @reference: Dynamic trees as search trees via euler tours, applied to the
 * network simplex algorithm by Robert E. Tarjan.
 * https://link.springer.com/article/10.1007/BF02614369
 */
class DynamicForest {
 private:
  static std::mt19937 rng_;

  struct Node {
    int size_;
    int priority_;

    Node* left_;
    Node* right_;
    Node* parent_;

    int from_;
    int to_;

    Node(int from, int to)
        : size_(1),
          priority_(rng_()),
          left_(nullptr),
          right_(nullptr),
          parent_(nullptr),
          from_(from),
          to_(to) {}

    void Maintain() {
      size_ = 1;
      if (left_) {
        size_ += left_->size_;
        left_->parent_ = this;
      }
      if (right_) {
        size_ += right_->size_;
        right_->parent_ = this;
      }
    }
  };

  static int GetSize(Node* p) { return p == nullptr ? 0 : p->size_; }

  static Node* FindRoot(Node* p) {
    if (!p) return nullptr;

    while (p->parent_ != nullptr) p = p->parent_;
    return p;
  }

  static std::string to_string(Node* p) {
    std::stringstream ss;

    ss << "Node [\n";

    std::function<void(Node*)> dfs = [&](Node* p) {
      if (!p) return;
      dfs(p->left_);
      ss << "(" << p->from_ << "," << p->to_ << "),";
      dfs(p->right_);
    };
    dfs(p);

    ss << "]\n\n";

    return ss.str();
  }

  Node* AllocateNode(int u, int v) {
    Node* p = new Node(u, v);
    return p;
  }

  void FreeNode(Node*& p) {
    if (p) {
      delete p;
      p = nullptr;
    }
  }

  /*
   * Dynamic Sequence Maintained using Treap.
   */
  class Treap {
   public:
    /**
     * Merge two treap a and b into a single treap, with keys in a less than
     * keys in b.
     *
     * In the other word, concating sequence a and sequence b.
     */
    static Node* Merge(Node* a, Node* b) {
      if (a == nullptr) return b;
      if (b == nullptr) return a;

      if (a->priority_ < b->priority_) {
        a->right_ = Merge(a->right_, b);
        a->Maintain();
        return a;
      } else {
        b->left_ = Merge(a, b->left_);
        b->Maintain();
        return b;
      }
    }

    /**
     * Get the number of nodes with keys less than or equal to the key of p.
     *
     * In the other word, the the 1-based index of p inside the sequencec
     * containing p.
     */
    static int GetPosition(Node* p) {
      assert(p != nullptr);

      int position = GetSize(p->left_) + 1;
      while (p) {
        if (p->parent_ && p == p->parent_->right_)
          position += GetSize(p->parent_->left_) + 1;
        p = p->parent_;
      }
      return position;
    }

    /**
     * Split sequence containning p into two sequences, the first one contains
     * the first k elements, the second one contains the remaining elements.
     */
    static std::pair<Node*, Node*> Split(Node* p, int k) {
      if (!p) return {nullptr, nullptr};

      std::pair<Node*, Node*> result;

      if (GetSize(p->left_) < k) {
        auto right_result = Split(p->right_, k - GetSize(p->left_) - 1);
        p->right_ = right_result.first;

        result.first = p;
        result.second = right_result.second;
      } else {
        auto left_result = Split(p->left_, k);
        p->left_ = left_result.second;

        result.first = left_result.first;
        result.second = p;
      }

      p->Maintain();

      if (result.first) result.first->parent_ = nullptr;

      if (result.second) result.second->parent_ = nullptr;

      return result;
    }

    /*
     * Bottom up split treap p into 2 treaps a and b.
     *   - a: a treap containing nodes with position less than or equal to p.
     *   - b: a treap containing nodes with postion greater than p.
     *
     * In the other word, split sequence containning p into two sequences, the
     * first one contains elements before p and element p, the second one
     * contains elements after p.
     */
    static std::pair<Node*, Node*> SplitUp2(Node* p) {
      assert(p != nullptr);

      Node *a = nullptr, *b = nullptr;
      b = p->right_;
      if (b) b->parent_ = nullptr;
      p->right_ = nullptr;

      bool is_p_left_child_of_parent = false;
      bool is_from_left_child = false;
      while (p) {
        Node* parent = p->parent_;

        if (parent) {
          is_p_left_child_of_parent = (parent->left_ == p);
          if (is_p_left_child_of_parent) {
            parent->left_ = nullptr;
          } else {
            parent->right_ = nullptr;
          }
          p->parent_ = nullptr;
        }

        if (!is_from_left_child) {
          a = Merge(p, a);
        } else {
          b = Merge(b, p);
        }

        is_from_left_child = is_p_left_child_of_parent;
        p->Maintain();
        p = parent;
      }

      return {a, b};
    }

    /*
     * Bottom up split treap p into 3 treaps a, b and c.
     *   - a: a treap containing nodes with key less than p.
     *   - b: a treap containing nodes with key greater than p.
     *   - c: a treap containing nodes with key equal p.
     *
     * In the other word, split sequence containning p into three sequences, the
     * first one contains elements before p, the second one contains element p,
     * the third one contains elements after p.
     */
    static std::tuple<Node*, Node*, Node*> SplitUp3(Node* p) {
      assert(p != nullptr);

      Node* a = p->left_;
      if (a) a->parent_ = nullptr;
      p->left_ = nullptr;

      Node* b = p->right_;
      if (b) b->parent_ = nullptr;
      p->right_ = nullptr;

      Node* c = p;

      bool is_p_left_child_of_parent = false;
      bool is_from_left_child = false;
      Node* parent = p->parent_;
      if (parent) {
        is_p_left_child_of_parent = (parent->left_ == p);
        if (is_p_left_child_of_parent) {
          parent->left_ = nullptr;
        } else {
          parent->right_ = nullptr;
        }
        p->parent_ = nullptr;
      }
      is_from_left_child = is_p_left_child_of_parent;
      p->Maintain();
      p = parent;

      while (p) {
        Node* parent = p->parent_;

        if (parent) {
          is_p_left_child_of_parent = (parent->left_ == p);
          if (is_p_left_child_of_parent) {
            parent->left_ = nullptr;
          } else {
            parent->right_ = nullptr;
          }
          p->parent_ = nullptr;
        }

        if (!is_from_left_child) {
          a = Merge(p, a);
        } else {
          b = Merge(b, p);
        }

        is_from_left_child = is_p_left_child_of_parent;
        p->Maintain();
        p = parent;
      }

      return {a, c, b};
    }
  };

 public:
  DynamicForest(int n) : n_(n), vertices_(n_), tree_edges_(n_) {
    assert(n_ > 0);

    for (int i = 0; i < n_; ++i) vertices_[i] = AllocateNode(i, i);
  }

  ~DynamicForest() {
    for (int i = 0; i < n_; ++i) {
      for (auto p : tree_edges_[i]) {
        FreeNode(p.second);
      }
    }
    for (int i = 0; i < n_; ++i) {
      FreeNode(vertices_[i]);
    }
  }

  void Insert(int u, int v) {
    assert(!tree_edges_[u].count(v));
    assert(!tree_edges_[v].count(u));

    Node* vertex_u = vertices_[u];
    Node* vertex_v = vertices_[v];

    Node* edge_uv = AllocateNode(u, v);
    Node* edge_vu = AllocateNode(v, u);
    tree_edges_[u][v] = edge_uv;
    tree_edges_[v][u] = edge_vu;

    int position_u = Treap::GetPosition(vertex_u);
    int position_v = Treap::GetPosition(vertex_v);

    auto p1 = Treap::SplitUp2(vertex_u);
    auto p2 = Treap::SplitUp2(vertex_v);
    auto L11 = p1.first, L12 = p1.second;
    auto L21 = p2.first, L22 = p2.second;

    assert(GetSize(L11) == position_u);
    assert(GetSize(L21) == position_v);

    Node* result = nullptr;
    result = Treap::Merge(result, L12);
    result = Treap::Merge(result, L11);
    result = Treap::Merge(result, edge_uv);
    result = Treap::Merge(result, L22);
    result = Treap::Merge(result, L21);
    result = Treap::Merge(result, edge_vu);
  }

  void Delete(int u, int v) {
    assert(tree_edges_[u].count(v));
    assert(tree_edges_[v].count(u));

    Node* edge_uv = tree_edges_[u][v];
    Node* edge_vu = tree_edges_[v][u];
    tree_edges_[u].erase(v);
    tree_edges_[v].erase(u);

    int position_uv = Treap::GetPosition(edge_uv);
    int position_vu = Treap::GetPosition(edge_vu);
    if (position_uv > position_vu) {
      std::swap(edge_uv, edge_vu);
      std::swap(position_uv, position_vu);
    }

    auto p1 = Treap::SplitUp3(edge_uv);
    auto L1 = std::get<0>(p1), uv = std::get<1>(p1);
    assert(GetSize(L1) == position_uv - 1);
    assert(GetSize(uv) == 1);

    auto p2 = Treap::SplitUp3(edge_vu);
    auto L2 = std::get<0>(p2), vu = std::get<1>(p2), L3 = std::get<2>(p2);
    assert(GetSize(L2) == position_vu - position_uv - 1);
    assert(GetSize(vu) == 1);

    L1 = Treap::Merge(L1, L3);

    FreeNode(edge_uv);
    FreeNode(edge_vu);
  }

  bool IsConnected(int u, int v) {
    Node* vertex_u = vertices_[u];
    Node* vertex_v = vertices_[v];
    return FindRoot(vertex_u) == FindRoot(vertex_v);
  }

  std::string to_string() const {
    std::stringstream ss;

    ss << "DynamicForest [\n";

    std::function<void(Node*)> dfs = [&](Node* p) {
      if (!p) return;
      dfs(p->left_);
      ss << "(" << p->from_ << "," << p->to_ << "),";
      dfs(p->right_);
    };
    for (int i = 0; i < n_; ++i) {
      if (vertices_[i]->parent_ == nullptr) {
        ss << "  Component [";
        dfs(vertices_[i]);
        ss << "]\n";
      }
    }
    for (int i = 0; i < n_; ++i) {
      for (auto p : tree_edges_[i]) {
        if (p.second->parent_ == nullptr) {
          ss << "  Component [";
          dfs(p.second);
          ss << "]\n";
        }
      }
    }

    ss << "]\n\n";

    return ss.str();
  }

 private:
  int n_;
  std::vector<Node*> vertices_;
  std::vector<std::map<int, Node*>> tree_edges_;
};

std::mt19937 DynamicForest::rng_(std::random_device{}());

void solve_case(int Case) {
  int n, m;
  std::cin >> n >> m;

  DynamicForest t(n + 1);
  std::string op;
  int u, v;
  for (int i = 1; i <= m; ++i) {
    std::cin >> op;
    std::cin >> u >> v;
    if (op[0] == 'Q') {
      std::cout << (t.IsConnected(u, v) ? "Yes" : "No") << "\n";
    } else if (op[0] == 'C') {
      t.Insert(u, v);
    } else if (op[0] == 'D') {
      t.Delete(u, v);
    }
  }
}

Duy trì thông tin cây con

Dưới đây lấy số lượng nút cây con làm ví dụ để giải thích.

Đối với mỗi phần tử trong \(\operatorname{ETR}(T)\), nếu phần tử đó tương ứng với một nút trong cây, thì gán trọng số của nó là \(1\); nếu phần tử đó tương ứng với một cạnh trong cây, thì gán trọng số của nó là \(0\). Số lượng nút của cây \(T\) lúc này có thể coi là tổng trọng số của các phần tử trong \(\operatorname{ETR}(T)\), chỉ cần duy trì tổng trọng số của dãy là có thể thực hiện duy trì số lượng nút cây con. Mà việc duy trì tổng trọng số của dãy là thao tác cổ điển của Treap không xoay.

Tương tự, có thể chuyển các thao tác như giá trị nhỏ nhất cây con thành các thao tác kinh điển của cây cân bằng trên dãy (ví dụ: tìm giá trị nhỏ nhất trên đoạn) rồi duy trì bằng cấu trúc dữ liệu tương ứng.

Bài toán ví dụ LOJ #2230.「BJOI2014」Hợp nhất lớn

Mã nguồn 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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <random>
#include <sstream>

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve_case(t);
  }
  return 0;
}

/**
 * Dynamic Forest Maintained With Euler Tour Tree.
 *
 * As said in reference, link and cut operation of dynamic trees can be
 * transformed into sequence split and sequence merge operation, which can be
 * easily maintained using balanced search trees like Treap.
 *
 * @reference: Dynamic trees as search trees via euler tours, applied to the
 * network simplex algorithm by Robert E. Tarjan.
 * https://link.springer.com/article/10.1007/BF02614369
 */
class DynamicForest {
 private:
  static std::mt19937 rng_;

  struct Node {
    int size_;
    int priority_;

    Node* left_;
    Node* right_;
    Node* parent_;

    int from_;
    int to_;

    int num_vertex_;
    int num_edge_;

    Node(int from, int to)
        : size_(1),
          priority_(rng_()),
          left_(nullptr),
          right_(nullptr),
          parent_(nullptr),
          from_(from),
          to_(to),
          num_vertex_(from_ == to_ ? 1 : 0),
          num_edge_(from_ == to_ ? 0 : 1) {}

    void Maintain() {
      size_ = 1;
      num_vertex_ = from_ == to_ ? 1 : 0;
      num_edge_ = from_ == to_ ? 0 : 1;
      if (left_) {
        size_ += left_->size_;
        left_->parent_ = this;

        num_vertex_ += left_->num_vertex_;
        num_edge_ += left_->num_edge_;
      }
      if (right_) {
        size_ += right_->size_;
        right_->parent_ = this;

        num_vertex_ += right_->num_vertex_;
        num_edge_ += right_->num_edge_;
      }
    }
  };

  static int GetSize(Node* p) { return p == nullptr ? 0 : p->size_; }

  static Node* FindRoot(Node* p) {
    if (!p) return nullptr;

    while (p->parent_ != nullptr) p = p->parent_;
    return p;
  }

  static std::string to_string(Node* p) {
    std::stringstream ss;

    ss << "Node [\n";

    std::function<void(Node*)> dfs = [&](Node* p) {
      if (!p) return;
      dfs(p->left_);
      ss << "(" << p->from_ << "," << p->to_ << "),";
      dfs(p->right_);
    };
    dfs(p);

    ss << "]\n\n";

    return ss.str();
  }

  Node* AllocateNode(int u, int v) {
    Node* p = new Node(u, v);
    return p;
  }

  void FreeNode(Node*& p) {
    if (p) {
      delete p;
      p = nullptr;
    }
  }

  /*
   * Dynamic Sequence Maintained using Treap.
   */
  class Treap {
   public:
    /**
     * Merge two treap a and b into a single treap, with keys in a less than
     * keys in b.
     *
     * In the other word, concating sequence a and sequence b.
     */
    static Node* Merge(Node* a, Node* b) {
      if (a == nullptr) return b;
      if (b == nullptr) return a;

      if (a->priority_ < b->priority_) {
        a->right_ = Merge(a->right_, b);
        a->Maintain();
        return a;
      } else {
        b->left_ = Merge(a, b->left_);
        b->Maintain();
        return b;
      }
    }

    /**
     * Get the number of nodes with keys less than or equal to the key of p.
     *
     * In the other word, the the 1-based index of p inside the sequencec
     * containing p.
     */
    static int GetPosition(Node* p) {
      assert(p != nullptr);

      int position = GetSize(p->left_) + 1;
      while (p) {
        if (p->parent_ && p == p->parent_->right_)
          position += GetSize(p->parent_->left_) + 1;
        p = p->parent_;
      }
      return position;
    }

    /**
     * Split sequence containning p into two sequences, the first one contains
     * the first k elements, the second one contains the remaining elements.
     */
    static std::pair<Node*, Node*> Split(Node* p, int k) {
      if (!p) return {nullptr, nullptr};

      std::pair<Node*, Node*> result;

      if (GetSize(p->left_) < k) {
        auto right_result = Split(p->right_, k - GetSize(p->left_) - 1);
        p->right_ = right_result.first;

        result.first = p;
        result.second = right_result.second;
      } else {
        auto left_result = Split(p->left_, k);
        p->left_ = left_result.second;

        result.first = left_result.first;
        result.second = p;
      }

      p->Maintain();

      if (result.first) result.first->parent_ = nullptr;

      if (result.second) result.second->parent_ = nullptr;

      return result;
    }

    /*
     * Bottom up split treap p into 2 treaps a and b.
     *   - a: a treap containing nodes with position less than or equal to p.
     *   - b: a treap containing nodes with postion greater than p.
     *
     * In the other word, split sequence containning p into two sequences, the
     * first one contains elements before p and element p, the second one
     * contains elements after p.
     */
    static std::pair<Node*, Node*> SplitUp2(Node* p) {
      assert(p != nullptr);

      Node *a = nullptr, *b = nullptr;
      b = p->right_;
      if (b) b->parent_ = nullptr;
      p->right_ = nullptr;

      bool is_p_left_child_of_parent = false;
      bool is_from_left_child = false;
      while (p) {
        Node* parent = p->parent_;

        if (parent) {
          is_p_left_child_of_parent = (parent->left_ == p);
          if (is_p_left_child_of_parent) {
            parent->left_ = nullptr;
          } else {
            parent->right_ = nullptr;
          }
          p->parent_ = nullptr;
        }

        if (!is_from_left_child) {
          a = Merge(p, a);
        } else {
          b = Merge(b, p);
        }

        is_from_left_child = is_p_left_child_of_parent;
        p->Maintain();
        p = parent;
      }

      return {a, b};
    }

    /*
     * Bottom up split treap p into 3 treaps a, b and c.
     *   - a: a treap containing nodes with key less than p.
     *   - b: a treap containing nodes with key greater than p.
     *   - c: a treap containing nodes with key equal p.
     *
     * In the other word, split sequence containning p into three sequences, the
     * first one contains elements before p, the second one contains element p,
     * the third one contains elements after p.
     */
    static std::tuple<Node*, Node*, Node*> SplitUp3(Node* p) {
      assert(p != nullptr);

      Node* a = p->left_;
      if (a) a->parent_ = nullptr;
      p->left_ = nullptr;

      Node* b = p->right_;
      if (b) b->parent_ = nullptr;
      p->right_ = nullptr;

      Node* c = p;

      bool is_p_left_child_of_parent = false;
      bool is_from_left_child = false;
      Node* parent = p->parent_;
      if (parent) {
        is_p_left_child_of_parent = (parent->left_ == p);
        if (is_p_left_child_of_parent) {
          parent->left_ = nullptr;
        } else {
          parent->right_ = nullptr;
        }
        p->parent_ = nullptr;
      }
      is_from_left_child = is_p_left_child_of_parent;
      p->Maintain();
      p = parent;

      while (p) {
        Node* parent = p->parent_;

        if (parent) {
          is_p_left_child_of_parent = (parent->left_ == p);
          if (is_p_left_child_of_parent) {
            parent->left_ = nullptr;
          } else {
            parent->right_ = nullptr;
          }
          p->parent_ = nullptr;
        }

        if (!is_from_left_child) {
          a = Merge(p, a);
        } else {
          b = Merge(b, p);
        }

        is_from_left_child = is_p_left_child_of_parent;
        p->Maintain();
        p = parent;
      }

      return {a, c, b};
    }
  };

 public:
  DynamicForest(int n) : n_(n), vertices_(n_), tree_edges_(n_) {
    assert(n_ > 0);

    for (int i = 0; i < n_; ++i) vertices_[i] = AllocateNode(i, i);
  }

  ~DynamicForest() {
    for (int i = 0; i < n_; ++i) {
      for (auto p : tree_edges_[i]) {
        FreeNode(p.second);
      }
    }
    for (int i = 0; i < n_; ++i) {
      FreeNode(vertices_[i]);
    }
  }

  void MakeRoot(int u) {
    Node* vertex_u = vertices_[u];

    int position_u = Treap::GetPosition(vertex_u);

    auto p1 = Treap::SplitUp2(vertex_u);
    auto L1 = p1.first, L2 = p1.second;
    assert(GetSize(L1) == position_u);

    Treap::Merge(L2, L1);
  }

  void Insert(int u, int v) {
    assert(!tree_edges_[u].count(v));
    assert(!tree_edges_[v].count(u));

    Node* vertex_u = vertices_[u];
    Node* vertex_v = vertices_[v];

    Node* edge_uv = AllocateNode(u, v);
    Node* edge_vu = AllocateNode(v, u);
    tree_edges_[u][v] = edge_uv;
    tree_edges_[v][u] = edge_vu;

    int position_u = Treap::GetPosition(vertex_u);
    int position_v = Treap::GetPosition(vertex_v);

    auto p1 = Treap::SplitUp2(vertex_u);
    auto p2 = Treap::SplitUp2(vertex_v);
    auto L11 = p1.first, L12 = p1.second;
    auto L21 = p2.first, L22 = p2.second;

    assert(GetSize(L11) == position_u);
    assert(GetSize(L21) == position_v);

    Node* result = nullptr;
    result = Treap::Merge(result, L12);
    result = Treap::Merge(result, L11);
    result = Treap::Merge(result, edge_uv);
    result = Treap::Merge(result, L22);
    result = Treap::Merge(result, L21);
    result = Treap::Merge(result, edge_vu);
  }

  void Delete(int u, int v) {
    assert(tree_edges_[u].count(v));
    assert(tree_edges_[v].count(u));

    Node* edge_uv = tree_edges_[u][v];
    Node* edge_vu = tree_edges_[v][u];
    tree_edges_[u].erase(v);
    tree_edges_[v].erase(u);

    int position_uv = Treap::GetPosition(edge_uv);
    int position_vu = Treap::GetPosition(edge_vu);
    if (position_uv > position_vu) {
      std::swap(edge_uv, edge_vu);
      std::swap(position_uv, position_vu);
    }

    auto p1 = Treap::SplitUp3(edge_uv);
    auto L1 = std::get<0>(p1), uv = std::get<1>(p1);
    assert(GetSize(L1) == position_uv - 1);
    assert(GetSize(uv) == 1);

    auto p2 = Treap::SplitUp3(edge_vu);
    auto L2 = std::get<0>(p2), vu = std::get<1>(p2), L3 = std::get<2>(p2);
    assert(GetSize(L2) == position_vu - position_uv - 1);
    assert(GetSize(vu) == 1);

    L1 = Treap::Merge(L1, L3);

    FreeNode(edge_uv);
    FreeNode(edge_vu);
  }

  bool IsConnected(int u, int v) {
    Node* vertex_u = vertices_[u];
    Node* vertex_v = vertices_[v];
    return FindRoot(vertex_u) == FindRoot(vertex_v);
  }

  int GetComponentSize(int u) {
    Node* vertex_u = vertices_[u];
    Node* root_of_vertex_u = FindRoot(vertex_u);
    return GetSize(root_of_vertex_u);
  }

  int GetComponentNumberOfVertex(int u) {
    Node* vertex_u = vertices_[u];
    Node* root_of_vertex_u = FindRoot(vertex_u);
    return root_of_vertex_u ? root_of_vertex_u->num_vertex_ : 0;
  }

  std::string to_string() const {
    std::stringstream ss;

    ss << "DynamicForest [\n";

    std::function<void(Node*)> dfs = [&](Node* p) {
      if (!p) return;
      dfs(p->left_);
      ss << "(" << p->from_ << "," << p->to_ << "),";
      dfs(p->right_);
    };
    for (int i = 0; i < n_; ++i) {
      if (vertices_[i]->parent_ == nullptr) {
        ss << "  Component [";
        dfs(vertices_[i]);
        ss << "]\n";
      }
    }
    for (int i = 0; i < n_; ++i) {
      for (auto p : tree_edges_[i]) {
        if (p.second->parent_ == nullptr) {
          ss << "  Component [";
          dfs(p.second);
          ss << "]\n";
        }
      }
    }

    ss << "]\n\n";

    return ss.str();
  }

 private:
  int n_;
  std::vector<Node*> vertices_;
  std::vector<std::map<int, Node*>> tree_edges_;
};

std::mt19937 DynamicForest::rng_(std::random_device{}());

void solve_case(int Case) {
  int n, q;
  std::cin >> n >> q;

  DynamicForest t(n + 1);
  std::string op;
  int u, v;
  for (int i = 1; i <= q; ++i) {
    std::cin >> op >> u >> v;
    if (op[0] == 'A') {
      t.Insert(u, v);
    } else if (op[0] == 'Q') {
      t.Delete(u, v);
      int ans = i64(1) * t.GetComponentNumberOfVertex(u) *
                t.GetComponentNumberOfVertex(v);
      t.Insert(u, v);
      std::cout << ans << "\n";
    }
  }
}

Duy trì thông tin đường đi cây

Có một kỹ thuật khá phổ biến là dựa vào tính chất của thứ tự ngoặc để chuyển đổi thông tin đường đi cây thành thông tin đoạn, sau đó có thể dựa vào cấu trúc dữ liệu duy trì dãy để duy trì thông tin đường đi cây. Tuy nhiên, kỹ thuật này yêu cầu thông tin cần duy trì phải có tính trừ được.

Các thao tác cây động tương ứng với dãy được giới thiệu trước đó có thể làm thay đổi thứ tự trước sau của dấu ngoặc phải so với dấu ngoặc trái trong thứ tự ngoặc, vì vậy khi duy trì các thông tin như tổng điểm nút trên đường đi cây, cần chú ý thêm, thao tác không được làm thay đổi thứ tự trước sau của dấu ngoặc tương ứng, mà điều này có thể cần suy nghĩ lại về thao tác trên dãy tương ứng với thao tác cây động, thậm chí suy nghĩ lại về việc duy trì thứ tự DFS nào.

Ngoài ra, ETT khó duy trì thao tác sửa đổi trên đường đi cây.

Bài toán ví dụ 「Thăm dò không gian」

Bài toán này thao tác cây động chỉ có đổi cha, có thể coi là xóa cạnh rồi thêm cạnh, nhưng cách này có thể làm thay đổi thứ tự trước sau của các dấu ngoặc tương ứng.

Có thể chuyển trọng số nút thành trọng số cạnh, duy trì thứ tự ngoặc của cây, thao tác đổi cha được chuyển đổi thành việc dịch chuyển toàn bộ dãy ngoặc tương ứng với cây con đến sau dấu ngoặc trái của nút cha.

Mã nguồn 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
/*
虽然上文提到过块状链表实现 ETT
在某些情况下可能较简单，但对于此题块状链表复杂度有可能无法通过而且实现较繁琐，所以这份代码采用
FHQ Treap 实现。
*/
#include <iostream>
#include <vector>
constexpr int N = 1000000;
using namespace std;
/*FHQ TREAP*/
long long rt, tot, f[N], rnd[N], ls[N], rs[N], siz[N], tag[N], val[N], sum[N],
    pd[N], pds[N];

void pushup(long long x) {
  siz[x] = siz[ls[x]] + siz[rs[x]] + 1;
  sum[x] = sum[ls[x]] + sum[rs[x]] + val[x];
  pds[x] = pds[ls[x]] + pds[rs[x]] + pd[x];
}

void link(long long x, long long c, long long y) {
  if (c)
    rs[x] = y;
  else
    ls[x] = y;
  if (y) f[y] = x;
  pushup(x);
}

long long newNode(long long x, long long y) {
  siz[++tot] = 1;
  val[tot] = sum[tot] = x;
  pd[tot] = pds[tot] = y;
  rnd[tot] = rand();
  return tot;
}

void setTag(long long x, long long v) {
  tag[x] += v;
  sum[x] += v * pds[x];
  val[x] += v * pd[x];
}

void pushdown(long long x) {
  if (ls[x]) setTag(ls[x], tag[x]);
  if (rs[x]) setTag(rs[x], tag[x]);
  tag[x] = 0;
}

void split(long long now, long long k, long long &x, long long &y) {
  f[now] = 0;
  if (!now) {
    x = y = 0;
    return;
  }
  pushdown(now);
  if (siz[ls[now]] + 1 <= k) {
    x = now;
    split(rs[now], k - siz[ls[now]] - 1, rs[x], y);
    link(x, 1, rs[x]);
  } else {
    y = now;
    split(ls[now], k, x, ls[y]);
    link(y, 0, ls[y]);
  }
}

long long merge(long long x, long long y) {
  if (!x || !y) return x | y;
  if (rnd[x] < rnd[y]) {
    pushdown(x);
    link(x, 1, merge(rs[x], y));
    return x;
  } else {
    pushdown(y);
    link(y, 0, merge(x, ls[y]));
    return y;
  }
}

long long rnk(long long x) {
  long long c = 1, ans = 0;
  while (x) {
    if (c) ans += siz[ls[x]] + 1;
    c = (rs[f[x]] == x);
    x = f[x];
  }
  return ans;
}

/*ETT*/
long long s[N], e[N];

void add(long long x, long long v) {
  long long a, b, c;
  split(rt, rnk(s[x]) - 1, a, b);
  split(b, rnk(e[x]) - rnk(s[x]) + 1, b,
        c);  // 这里 b 是我们要进行操作的子树的括号序列。
  setTag(b, v);
  rt = merge(merge(a, b), c);
}

long long query(long long x) {
  long long a, b;
  split(rt, rnk(s[x]), a, b);
  long long ans = sum[a];
  rt = merge(a, b);
  return ans;
}

void changeFa(long long x, long long y) {
  long long a, b, c, d;
  split(rt, rnk(s[x]) - 1, a, b);
  split(b, rnk(e[x]) - rnk(s[x]) + 1, b, c);
  a = merge(
      a,
      c);  // 因为我们确定不了要设置为父亲的节点在括号序列中的哪边，所以先把两边合并。
  split(a, rnk(s[y]), a, d);
  rt = merge(merge(a, b), d);  // 把要进行操作的子树放在父亲括号序列的最前面。
}

/*main function*/
long long n, m, w[N];
vector<long long> v[N];

void dfs(long long x) {
  rt = merge(rt, s[x] = newNode(w[x], 1));
  for (auto to : v[x]) dfs(to);
  rt = merge(rt, e[x] = newNode(-w[x], -1));
}

signed main() {
  cin >> n;
  for (long long i = 2; i <= n; i++) {
    long long f;
    cin >> f;
    v[f].push_back(i);
  }
  for (long long i = 1; i <= n; i++) cin >> w[i];
  dfs(1);
  cin >> m;
  for (long long i = 1; i <= m; i++) {
    char c;
    cin >> c;
    if (c == 'Q') {
      long long d;
      cin >> d;
      cout << query(d) << endl;
    } else if (c == 'C') {
      long long x, y;
      cin >> x >> y;
      changeFa(x, y);
    } else {
      long long p, q;
      cin >> p >> q;
      add(p, q);
    }
  }
  return 0;
}

Tài liệu tham khảo

  • Dynamic trees as search trees via euler tours, applied to the network simplex algorithm - Robert E. Tarjan
  • Randomized fully dynamic graph algorithms with polylogarithmic time per operation - Henzinger et al.
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