Skip to content

Euler Tour Tree

An Euler tour tree (ETT) is a data structure for dynamic tree problems. It turns each operation on a dynamic tree into range operations on a DFS sequence of the tree, and leaves those to another data structure that maintains the sequence. Adding an edge, for example, becomes a few splits and merges of sequences, so a structure that can split and merge sequences can add edges to a dynamic tree.

The LCT is another data structure for dynamic tree problems, and the more common of the two. An LCT is really better suited to information about tree paths, and an ETT to information about subtrees. For example, an ETT can maintain subtree minima and an LCT cannot.

Any data structure can sit underneath an ETT, as long as it supports the required range operations on a sequence within the required complexity. The usual choice is a balanced binary search tree such as a splay tree or a treap. These perform range operations in \(O(\log n)\), so the dynamic tree operations take \(O(\log n)\) time as well. With a multiway balanced search tree such as a B-tree, the complexity can be improved further.

An ETT is best seen as an idea: maintain a sequence that is in one-to-one correspondence with the original tree, and you maintain the tree. This article presents only some workable implementations and applications of that idea.

Euler tour representation of a tree

If each tree edge is regarded as two directed edges, a tree can be represented as an Eulerian circuit of a directed graph. This is called the Euler tour representation (ETR) of the tree.

The sequence maintained below is actually a variant of the ETR: the nodes of the tree are treated as self-loops and put into it as well. The authors of the original paper gave the variant no name of its own, so we call it the ETR too.

The following algorithm computes the Euler tour representation of a tree \(T\):

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{A rooted tree }T\\ 2 & \textbf{Output. } \text{The dfs sequence of rooted tree }T\\ 3 & \operatorname{ET}(u)\\ 4 & \qquad \text{visit vertex }u\\ 5 & \qquad \text{for all children } v \text{ of } u\\ 6 & \qquad \qquad \text{visit directed edge } u \to v\\ 7 & \qquad \qquad \operatorname{ET}(v)\\ 8 & \qquad \qquad \text{visit directed edge } v \to u\\ \end{array} \]

The Euler tour representation \(\operatorname{ETR}(T)\) of \(T\) starts out empty. Whenever the DFS visits a node or a directed edge, append it to the end of \(\operatorname{ETR}(T)\). When the DFS ends, the representation is complete.

If \(T\) has \(n\) nodes, it has \(2n - 2\) directed edges. The DFS visits every node and every directed edge exactly once, so \(\operatorname{ETR}(T)\) has length \(3n - 2\).

Treat each node \(u\) as a self-loop. Then \(\operatorname{ETR}(T)\) is an Eulerian circuit of a directed graph. The circuit can be cut open at any point, which leaves a path of edges joined head to tail. Such a path can be glued back together at the cut to recover the circuit, and two such paths can be spliced into a new Eulerian circuit by adding a few edges.

Unless stated otherwise, the sequence maintained in the rest of this article is the Euler tour representation of the tree.

Basic operations of an ETT

The following 3 operations are the basic operations of an ETT. Each reduces to a constant number of sequence operations, so its complexity is of the same order as that of a sequence operation.

What is given here is only one possible implementation. Any way of assembling the sequence of the modified tree from a constant number of sequence operations will do.

MakeRoot(u)

This is the rerooting operation. In an ETT it becomes 1 split and 1 merge of sequences, or, seen another way, 1 range shift.

Let \(T\) be the tree containing node \(u\) and \(r\) its current root; we want to make \(u\) the root. Let \(L\) be the sequence of \(T\). Split \(L\) at \((u, u)\) into sequences \(L^1\) and \(L^2\): the first contains \((u, u)\) and the elements of \(L\) before it, the second contains the rest. Merging \(L^2\) and \(L^1\), in that order, gives the sequence of the rerooted tree.

Think of this as rotating an Eulerian circuit. The circuit is a cycle, so rotating it does not change its structure, and hence does not change the structure of the tree either: it only rotates node \(u\) into the root position.

Insert(u, v)

This operation adds an edge. In an ETT it becomes 2 splits and 5 merges of sequences.

Let \(T_1\) be the tree containing node \(u\) and \(T_2\) the tree containing node \(v\); adding the edge merges them into one tree \(T\). Let \(L_1\) be the sequence of \(T_1\) and \(L_2\) the sequence of \(T_2\).

Split \(L_1\) at \((u, u)\) into sequences \(L_1^1\) and \(L_1^2\): the first contains \((u, u)\) and the elements of \(L_1\) before it, the second contains the rest. Split \(L_2\) at \((v, v)\) into \(L_2^1\) and \(L_2^2\) in the same way. Merging \(L_1^2, L_1^1, [(u, v)], L_2^2, L_2^1, [(v, u)]\) in that order gives the sequence \(L\) of \(T\).

Think of this as two rerootings, after which the two Eulerian circuits are cut open at their current roots and spliced into a new Eulerian circuit by the two new directed edges.

Delete(u, v)

This operation deletes an edge. In an ETT it becomes 4 splits and 1 merge of sequences.

Let \(T\) be the tree containing the edges \((u, v)\) and \((v, u)\), and let \(L\) be its sequence. Deleting the edge splits \(T\) into two trees.

Split \(L\) into \(L_1, [(u, v)], L_2, [(v, u)], L_3\). The sequences of the two resulting trees are \(L_2\) and \(L_1, L_3\). Note that \([(u, v)]\) may come after \([(v, u)]\) in \(L\); in that case, swap \(u\) and \(v\) first.

Think of this as cutting an Eulerian circuit at the two directed edges, which leaves two paths; each path then closes up, head to tail, into a new Eulerian circuit.

Implementation

This section implements an ETT on top of a non-rotating treap. You should already know how a non-rotating treap handles range operations.

Split and Merge are the basic operations of a non-rotating treap, so we do not repeat them here.

SplitUp2(u)

Let \(L\) be the sequence containing \(u\). Split \(L\) at \(u\) into sequences \(L^1\) and \(L^2\): the first contains \(u\) and the elements of \(L\) before it, the second contains the rest.

If every treap node also stores its parent, the position in the sequence of the element that a treap node represents can be computed in \(O(\log n)\) time. Calling Split with that position then does the job.

The split can also be done bottom-up, which is more efficient. Climb from the node of \(u\) to the root. By the binary search tree property, we can tell for each node on the way whether it comes before or after \(u\) in \(L\). That is enough to compute the position of \(u\) in the sequence, and also to decide which of the two resulting trees each node belongs to.

 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 position greater than p.
 *
 * In the other word, split sequence containing 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)

Let \(L\) be the sequence containing \(u\). Split \(L\) at \(u\) into sequences \(L^1\), \(u\) and \(L^2\): the first contains the elements of \(L\) before \(u\), the last contains the rest.

A small change to SplitUp2 is all it takes.

MakeRoot(u)

This follows directly from SplitUp2 and 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)

This follows directly from SplitUp2 and 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)

This follows directly from SplitUp3 and 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);
}

Maintaining connectivity

Nodes \(u\) and \(v\) are connected if and only if they belong to the same tree \(T\), that is, if \((u, u)\) and \((v, v)\) both belong to \(\operatorname{ETR}(T)\). To test this, check whether the treap nodes of \(u\) and \(v\) lie in treaps with the same root.

Example: P2147 [SDOI2008] Cave Survey

A template problem for maintaining connectivity.

Reference code
  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, concatenating 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 1-based index of p inside the sequence
     * 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 containing 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 position greater than p.
     *
     * In the other word, split sequence containing 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 containing 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);
    }
  }
}

Maintaining subtree information

We take the number of nodes in a subtree as the example.

Give every element of \(\operatorname{ETR}(T)\) a weight: \(1\) if it corresponds to a node of the tree, \(0\) if it corresponds to an edge. The number of nodes of \(T\) is then the sum of the weights of the elements of \(\operatorname{ETR}(T)\), so maintaining the sum of weights over a sequence is all it takes to maintain subtree sizes. And that is a classic operation on a non-rotating treap.

Similarly, operations such as subtree minimum reduce to classic balanced tree operations such as the minimum of a sequence.

Example: LOJ #2230. [BJOI2014] Great Merge

Reference code
  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, concatenating 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 1-based index of p inside the sequence
     * 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 containing 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 position greater than p.
     *
     * In the other word, split sequence containing 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 containing 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";
    }
  }
}

Maintaining path information

A fairly common trick uses the properties of the bracket sequence to turn path information into range information; a data structure that maintains the sequence then maintains the path information. But the trick requires the information to be subtractable.

The sequence operations given above for the dynamic tree operations may move a closing bracket of the bracket sequence in front of its opening bracket. So maintaining something like the sum of vertex weights on a path takes extra care: no operation may change the order of a matching pair of brackets. This may mean rethinking which sequence operations implement the dynamic tree operations, or even which DFS order to maintain.

Path updates, moreover, are hard to support with an ETT.

Example: Interstellar Exploration

The only dynamic tree operation in this problem is changing a node's parent. It can be seen as deleting an edge and then adding one, but done that way it may change the order of matching brackets.

Instead, turn the vertex weights into edge weights and maintain the bracket sequence of the tree. Changing a parent then becomes shifting the bracket sequence of the whole subtree to just after the opening bracket of its new parent.

Reference code
  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
/*
The text above mentioned that implementing an ETT with an unrolled linked list
can be simpler in some cases. For this problem, though, it may be too slow to pass and is tedious to write, so this code uses
an 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);  // Here b is the bracket sequence of the subtree we operate on.
  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);  // The new parent may lie on either side in the bracket sequence, so merge the two sides first.
  split(a, rnk(s[y]), a, d);
  rt = merge(merge(a, b), d);  // Put the subtree we operate on at the very front of the parent's bracket sequence.
}

/*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;
}

References

  • 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.