跳转至

# Euler Tour Tree

Euler Tour Tree（欧拉游览树，欧拉回路树，后文简称 ETT）是一种可以解决 动态树 问题的数据结构．ETT 将动态树的操作转换成了其 DFS 序列上的区间操作，再用其他数据结构来维护序列的区间操作，从而维护动态树的操作．例如，ETT 将动态树的加边操作转换成了多个序列拆分操作和序列合并操作，如果能维护序列拆分操作和序列合并操作，就能维护动态树的加边操作．

LCT 也是一种可以解决动态树问题的数据结构，相比 ETT 而言 LCT 会更加常见．LCT 其实更适用于维护树链的信息，而 ETT 更加适用于维护 子树 的信息．例如，ETT 可以维护子树最小值而 LCT 不能．

ETT 可以使用任意数据结构维护，只需要该数据结构支持对应的序列区间操作，以及在复杂度上满足要求．一般情况下会使用例如 Splay，Treap 等平衡二叉搜索树来维护序列，而这些数据结构维护区间操作的复杂度均为 𝑂(l o g⁡𝑛)O(log⁡n)，由此也可以在 𝑂(l o g⁡𝑛)O(log⁡n) 的时间内维护动态树的操作．如果使用多叉平衡搜索树例如 B 树来维护区间操作，也可以做到更优的复杂度．

其实 ETT 可以理解为一种思想，就是通过维护某种和原树一一对应的序列，从而达到维护原树的目的，本文介绍的只是这个思想的一些可行的实现和应用．

## 树的欧拉回路表示

如果把一条树边看成两条有向边的话，那么就可以把一棵树表示成一个有向图的欧拉回路，称为树的欧拉回路表示（Euler tour representation，ETR）．

后面要维护的序列其实是 ETR 的一个变种，把树中的点看成了自环也加到了 ETR 中，但是由于原始论文中作者没有给它起新的名字，就还是叫它 ETR 吧．

可以通过下述算法得到树 𝑇 T 的 欧拉回路表示：

1 𝐈 𝐧 𝐩 𝐮 𝐭. A r o o t e d t r e e 𝑇 2 𝐎 𝐮 𝐭 𝐩 𝐮 𝐭. T h e d f s s e q u e n c e o f r o o t e d t r e e 𝑇 3 E T⁡(𝑢)4 v i s i t v e r t e x 𝑢 5 f o r a l l c h i l d 𝑣 o f 𝑢 6 v i s i t d i r e c t e d e d g e 𝑢→𝑣 7 E T⁡(𝑣)8 v i s i t d i r e c t e d e d g e 𝑣→𝑢 1 Input. A rooted tree T 2 Output. The dfs sequence of rooted tree T 3 ET⁡(u)4 visit vertex u 5 for all child v of u 6 visit directed edge u→v 7 ET⁡(v)8 visit directed edge v→u

树 𝑇 T 的欧拉回路表示 E T R⁡(𝑇)ETR⁡(T) 初始为空，DFS 的过程中每次访问一个节点或者一条有向边时就将其加到 E T R⁡(𝑇)ETR⁡(T) 的尾部，如此便可得到 E T R⁡(𝑇)ETR⁡(T)．

若 𝑇 T 中包含 𝑛 n 个节点，则中包含 2 𝑛 −2 2 n−2 条有向边，而 DFS 的过程中，每个点和每条有向边都会被访问一次，所以 E T R⁡(𝑇)ETR⁡(T) 的长度为 3 𝑛 −2 3 n−2．

把点 𝑢 u 看成是一个自环，这样 E T R⁡(𝑇)ETR⁡(T) 就可以看成有向图中的一个欧拉回路．可以在欧拉回路的某处断开，将其看成是一些边的首尾相连组成的链；也可以把这样的链在断开处重新粘起来变回欧拉回路；还可以通过新增一些边把两个这样的链拼成一个新的欧拉回路．

后文中，如未说明默认维护的序列是树的欧拉回路表示．

## ETT 的基本操作

以下 3 个操作算是 ETT 的基本操作，均可以转换成常数次序列的操作，所以这 3 个操作的复杂度和序列操作同阶．

这里给出的只是一种可行的实现，只要能用常数次序列操作把修改后对应的序列拼出来即可．

### MakeRoot(u)

即换根操作．ETT 中的换根操作被转换成了 1 个序列拆分操作和 1 个序列合并操作，也可以理解成 1 个区间平移操作．

记包含点 𝑢 u 的树为 𝑇 T，当前其树根为 𝑟 r，现在要将树根换成 𝑢 u．树 𝑇 T 对应的序列为 𝐿 L，将 𝐿 L 在 (𝑢,𝑢)(u,u) 处拆分成序列 𝐿 1 L 1 和 𝐿 2 L 2，前者包含 𝐿 L 中 (𝑢,𝑢)(u,u) 之前的元素以及 (𝑢,𝑢)(u,u)，后者包含剩余元素．则依次将 𝐿 2 L 2 和 𝐿 1 L 1 合并得到的序列，即为换根之后树对应的序列．

这里可以理解成对一个欧拉回路进行旋转操作，欧拉回路是一个环，旋转并不会改变欧拉回路的结构，也即不会改变树的结构，只是把点 𝑢 u 旋转到了根的位置而已．

### Insert(u, v)

即加边操作．ETT 中加边操作被转换成了 2 个序列拆分操作和 5 个序列合并操作．

记包含点 𝑢 u 的树为 𝑇 1 T 1，包含点 𝑣 v 的树为 𝑇 2 T 2，加边之后两颗树合并成了一颗树 𝑇 T．树 𝑇 1 T 1 对应的序列为 𝐿 1 L 1，树 𝑇 2 T 2 对应的序列为 𝐿 2 L 2．

将 𝐿 1 L 1 在 (𝑢,𝑢)(u,u) 处拆分成序列 𝐿 1 1 L 1 1 和 𝐿 2 1 L 1 2，前者包含 𝐿 1 L 1 中 (𝑢,𝑢)(u,u) 之前的元素以及 (𝑢,𝑢)(u,u)，后者包含剩余元素．类似地将 𝐿 2 L 2 在 (𝑣,𝑣)(v,v) 处拆分成序列 𝐿 1 2 L 2 1 和 𝐿 2 2 L 2 2．则依次将 𝐿 2 1,𝐿 1 1,[(𝑢,𝑣)],𝐿 2 2,𝐿 1 2,[(𝑣,𝑢)]L 1 2,L 1 1,[(u,v)],L 2 2,L 2 1,[(v,u)] 合并即可得到树 𝑇 T 对应的序列 𝐿 L．

这里可以理解成两次换根操作，然后把两个欧拉回路在当前根的位置处断开，再用新加的两条有向边把两个欧拉回路拼成一个新的欧拉回路．

### Delete(u, v)

即删边操作．ETT 中删边操作被转换成了 4 个序列拆分操作以及 1 个序列合并操作．

记包含边 (𝑢,𝑣)(u,v) 和边 (𝑣,𝑢)(v,u) 的树为 𝑇 T，其对应序列为 𝐿 L．删边之后 𝑇 T 分成了两颗树．

将 𝐿 L 拆分成 𝐿 1,[(𝑢,𝑣)],𝐿 2,[(𝑣,𝑢)],𝐿 3 L 1,[(u,v)],L 2,[(v,u)],L 3，删边形成的两颗树对应的序列分别为 𝐿 2 L 2 以及 𝐿 1,𝐿 3 L 1,L 3．注意，在序列 𝐿 L 中 [(𝑢,𝑣)][(u,v)] 有可能出现在 [(𝑣,𝑢)][(v,u)] 的后面，此时可以先交换 𝑢 u 和 𝑣 v 的值然后再操作．

这里可以理解成把一个欧拉回路从两条有向边处断开形成两条链，然后两条链自己首尾相连形成两个新的欧拉回路．

## 实现

以下以非旋 Treap 为例介绍 ETT 的实现，需要读者事先了解使用非旋 Treap 维护区间操作的相关内容．

`Split` 和 `Merge` 都是非旋 Treap 的基本操作了，这里不再赘述．

### SplitUp2(u)

假设 𝑢 u 所在的序列为 𝐿 L，将 𝐿 L 在 𝑢 u 处拆分成序列 𝐿 1 L 1 和 𝐿 2 L 2，前者包含 𝐿 L 中 𝑢 u 之前的元素以及 𝑢 u，后者包含剩余元素．

如果 Treap 的每个节点额外维护自己的父亲的话，就可以实现 𝑂(l o g⁡𝑛)O(log⁡n) 的时间内计算一个 Treap 节点对应的元素在序列中的位置，再根据位置去 `Split` 就可以实现上述功能．

也可以自底向上地拆分从而实现上述功能，这样做相比上述方法会更高效．具体就是，在从 𝑢 u 对应的节点往根跳的过程中，根据二叉搜索树的性质就可以确定每个节点在 𝐿 L 中位于 𝑢 u 之前还是之后，根据这点就可以计算 𝑢 u 在序列中的位置，也可以确定每个节点属于拆分后的哪一棵树．

     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)

假设 𝑢 u 所在的序列为 𝐿 L，将 𝐿 L 在 𝑢 u 处拆分成序列 𝐿 1 L 1,𝑢 u 和 𝐿 2 L 2，前者包含 𝐿 L 中 𝑢 u 之前的元素，后者包含剩余元素．

在 `SplitUp2` 的基础上稍作修改即可．

### MakeRoot(u)

基于 `SplitUp2` 以及 `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)

基于 `SplitUp2` 以及 `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)

基于 `SplitUp3` 以及 `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);
    }

## 维护连通性

点 𝑢 u 和点 𝑣 v 连通，当且仅当两个点属于同一棵树 𝑇 T，即 (𝑢,𝑢)(u,u) 和 (𝑣,𝑣)(v,v) 属于 E T R⁡(𝑇)ETR⁡(T)，这可以根据点 𝑢 u 和点 𝑣 v 对应的 Treap 节点所在的 Treap 的根是否相同判断．

### 例题 P2147[SDOI2008] 洞穴勘测

维护连通性的模板题．

参考代码

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

## 维护子树信息

下面以子树节点数量为例进行说明．

对于 E T R⁡(𝑇)ETR⁡(T) 中每一个元素，如果这个元素对应的是树中的点，则令其权值为 1 1；如果这个元素对应的是树中的边，则令其权值为 0 0．现在树 𝑇 T 的节点数量就可以看成 E T R⁡(𝑇)ETR⁡(T) 中元素的权值和，只需要再维护序列权值和即可实现维护子树节点数量．而序列权值和的维护是非旋 Treap 的经典操作了．

类似地，可以将子树最小值等操作转化成序列最小值等平衡树经典操作然后维护．

### 例题 LOJ #2230.「BJOI2014」大融合

参考代码

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

## 维护树链信息

可以使用一个比较常见的技巧就是借助括号序的性质将树链信息转化成区间信息，然后就可以借助数据结构维护序列从而维护树链信息了．但是这个技巧要求维护的信息满足 可减性．

前面介绍的动态树操作对应的序列操作可能会把括号序中的右括号移动到左括号前，所以维护树链点权和之类的信息时还需要额外注意，操作时不能改变对应左右括号的先后顺序，而这可能需要重新思考动态树操作对应的序列操作，甚至重新思考维护什么 DFS 序．

此外，ETT 很难维护树链修改．

### 例题 「星际探索」

这题的动态树操作只有换父亲，可以看成删边再加边，但是这样可能会改变对应括号的先后顺序．

可以把点权转成边权，维护树的括号序，换父亲操作转化成把整个子树对应的括号序列平移至父亲左括号后面．

参考代码

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

## 参考资料

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

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, Backl1ght, Enter-tainer, hsfzLZH1, ksyx, Tiphereth-A, c-forrest, ChungZH, hqztrue, kenlig, mcendu, Molmin, partychicken, StudyingFather, swiftqwq, WillHouMoe, Xarfa
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用