AIOJ

The Euler Tour Tree (also called an Euler traversal tree or Euler circuit tree, abbreviated ETT below) is a data structure that can solve dynamic tree problems. ETT converts operations on a dynamic tree into interval operations on its DFS sequence, and then uses another data structure to maintain interval operations on the sequence, thereby maintaining operations on the dynamic tree. For example, ETT converts adding an edge to a dynamic tree into several sequence split and sequence merge operations; if sequence splits and merges can be maintained, adding an edge to the dynamic tree can be maintained as well．

LCT is also a data structure for dynamic tree problems, and is more common than ETT. LCT is better suited to maintaining information on tree paths, while ETT is better suited to maintaining subtree information. For example, ETT can maintain subtree minimums, whereas LCT cannot．

ETT can be maintained with any data structure, provided that the data structure supports the corresponding sequence interval operations and meets the required complexity. In general, balanced binary search trees such as Splay trees and Treaps are used to maintain the sequence. These data structures support interval operations in $O(\log n)$ time, so dynamic-tree operations can also be maintained in $O(\log n)$ time. If a multiway balanced search tree such as a B-tree is used, an even better complexity is possible．

ETT can actually be understood as an idea: maintain a sequence in one-to-one correspondence with the original tree to maintain the original tree. This article introduces only some feasible implementations and applications of this idea．

Euler Tour Representation of a Tree

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

The sequence maintained below is actually a variant of ETR: vertices in the tree are also treated as self-loops and added to the ETR. Since the authors of the original paper did not give it a new name, we will still call it ETR．

The Euler tour representation of a tree $T$ can be obtained by the following algorithm:

\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 child } 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 tree $T$ is initially empty. During DFS, whenever a vertex or a directed edge is visited, it is appended to the end of $\operatorname{ETR}(T)$ , producing $\operatorname{ETR}(T)$ ．

If $T$ contains $n$ vertices, it contains $2n - 2$ directed edges. During DFS, every vertex and every directed edge is visited once, so the length of $\operatorname{ETR}(T)$ is $3n - 2$ ．

Treating vertex $u$ as a self-loop makes $\operatorname{ETR}(T)$ an Euler tour in a directed graph. The tour can be cut at some point and viewed as a chain made of edges joined end to end; such a chain can also be joined back at the cut to recover the Euler tour. Two such chains can additionally be joined into a new Euler tour by adding some edges．

Unless otherwise stated, the sequence maintained below is the Euler tour representation of a tree．

Basic ETT Operations

The following three operations are the basic ETT operations. Each can be converted into a constant number of sequence operations, so its complexity is of the same order as the sequence operations．

The implementations below are only one possible approach; any method that constructs the sequence after a modification using a constant number of sequence operations is valid．

MakeRoot(u)

This is the rerooting operation. In ETT, rerooting is converted into one sequence split and one sequence merge, or equivalently one interval shift．

Let the tree containing vertex $u$ be $T$ , with current root $r$ , and suppose we want to make $u$ the root. Let $L$ be the sequence corresponding to $T$ . Split $L$ at $(u, u)$ into $L^1$ and $L^2$ , where the former contains the elements before $(u, u)$ in $L$ together with $(u, u)$ , and the latter contains the remaining elements. Merging $L^2$ and $L^1$ in that order gives the sequence corresponding to the rerooted tree．

This can be understood as rotating an Euler tour. An Euler tour is a cycle, so rotation does not change its structure or the structure of the tree; it merely rotates vertex $u$ into the root position．

Insert(u, v)

This is the edge-addition operation. In ETT, adding an edge is converted into two sequence splits and five sequence merges．

Let the tree containing $u$ be $T_1$ and the tree containing $v$ be $T_2$ . After adding the edge, they become one tree $T$ . The sequence for tree $T_1$ is $L_1$ , and that for tree $T_2$ is $L_2$ ．

Split $L_1$ at $(u, u)$ into $L_1^1$ and $L_1^2$ , where the former contains the elements before $(u, u)$ in $L_1$ and $(u, u)$ itself, and the latter contains the remainder. Similarly split $L_2$ at $(v, v)$ into $L_2^1$ and $L_2^2$ . Merging $L_1^2, L_1^1, [(u, v)], L_2^2, L_2^1, [(v, u)]$ in order produces the sequence $L$ for $T$ ．

This can be understood as rerooting twice, cutting the two Euler tours at their current roots, and joining them into a new Euler tour with the two newly added directed edges．

Delete(u, v)

This is the edge-deletion operation. In ETT, deleting an edge is converted into four sequence splits and one sequence merge．

Let $T$ be the tree containing edges $(u, v)$ and $(v, u)$ , with corresponding sequence $L$ . After deleting the edge, $T$ splits 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$ , respectively. Note that $[(u, v)]$ may occur after $[(v, u)]$ in $L$ ; in that case, swap the values of $u$ and $v$ first．

This can be understood as cutting an Euler tour at the two directed edges to form two chains, then joining the ends of each chain to form two new Euler tours．

Implementation

The implementation of ETT below uses a non-rotating Treap as an example. Readers should already be familiar with using a non-rotating Treap to maintain interval operations．

Split and Merge are basic operations of a non-rotating Treap and will not be explained here．

SplitUp2(u)

Suppose the sequence containing $u$ is $L$ . Split $L$ at $u$ into $L^1$ and $L^2$ , where the former contains the elements before $u$ in $L$ and $u$ itself, and the latter contains the remaining elements．

If every Treap node additionally stores its parent, the position of the element corresponding to a Treap node in the sequence can be found in $O(\log n)$ time, after which Split at that position implements the operation above．

The same operation can also be implemented by splitting from the bottom up, which is more efficient. While moving from the node corresponding to $u$ toward the root, the binary-search-tree property determines whether each node lies before or after $u$ in $L$ . This determines the position of $u$ in the sequence and which of the two split trees each node belongs to．

/*
 * 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)

Suppose the sequence containing $u$ is $L$ . Split $L$ at $u$ into $L^1$ , $u$ , and $L^2$ , where the former contains the elements before $u$ in $L$ and the latter contains the remaining elements．

This can be implemented by making a small modification to SplitUp2．

MakeRoot(u)

This follows directly from SplitUp2 and Merge．

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．

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．

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

Vertices $u$ and $v$ are connected if and only if they belong to the same tree $T$ , that is, $(u, u)$ and $(v, v)$ belong to $\operatorname{ETR}(T)$ . This can be determined by checking whether the Treap roots of the Treap nodes corresponding to $u$ and $v$ are the same．

Example P2147[SDOI2008] Cave Exploration

A standard problem for maintaining connectivity．

Reference code

#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 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 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);
    }
  }
}

Maintaining Subtree Information

The following uses the number of subtree vertices as an example．

For every element in $\operatorname{ETR}(T)$ , assign weight $1$ if it corresponds to a vertex of the tree, and weight $0$ if it corresponds to an edge. The number of vertices in tree $T$ can then be viewed as the sum of the weights of the elements in $\operatorname{ETR}(T)$ . Maintaining subtree vertex counts therefore only requires maintaining the sequence sum, a standard operation for a non-rotating Treap．

Similarly, operations such as subtree minimums can be converted into standard balanced-tree operations such as sequence minimums and maintained．

Example LOJ #2230.「BJOI2014」Big Fusion

Reference code

#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 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 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";
    }
  }
}

Maintaining Tree-Path Information

A common technique is to use the properties of a parenthesis sequence to convert tree-path information into interval information, and then maintain the sequence with a data structure. However, this technique requires the maintained information to be subtractive.

The sequence operations corresponding to the dynamic-tree operations described above may move a closing parenthesis before an opening parenthesis in the parenthesis sequence. Therefore, when maintaining information such as the sum of vertex weights on a tree path, extra care is needed: the relative order of the corresponding parentheses must not change. This may require reconsidering the sequence operations corresponding to dynamic-tree operations, or even reconsidering which DFS order to maintain.

In addition, ETT is difficult to use for maintaining tree-path updates.

Example: Interstellar Exploration

The only dynamic-tree operation in this problem is changing a parent. It can be viewed as deleting an edge and then adding an edge, but this may change the relative order of the corresponding parentheses.

We can convert vertex weights to edge weights, maintain the tree's parenthesis sequence, and turn a change-parent operation into shifting the entire parenthesis subsequence for a subtree to immediately after the parent's opening parenthesis.

Reference Code

/*
Although a block-linked-list implementation of ETT was mentioned above,
it may be simpler in some cases, but its complexity may not pass this problem and its implementation is cumbersome, so this code uses
an FHQ Treap implementation.
*/
#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 is the parenthesis sequence of the subtree to 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);  // We cannot determine which side of the parenthesis sequence contains the new parent, so merge both sides first.
  split(a, rnk(s[y]), a, d);
  rt = merge(merge(a, b), d);  // Put the subtree being operated on immediately before the parent's parenthesis 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.