Euler Tour Tree (ETT) is a data structure that can solve dynamic tree problems. ETT transforms operations on dynamic trees into interval operations on their DFS sequences, then uses other data structures to maintain these interval operations, thereby maintaining the dynamic tree operations. For example, ETT transforms the edge addition operation in dynamic trees into multiple sequence split and merge operations. If sequence split and merge operations can be maintained, then dynamic tree edge addition can be maintained.
Link-Cut Tree (LCT) is another data structure that can solve dynamic tree problems, and is more commonly seen compared to ETT. LCT is actually more suitable for maintaining information on tree paths, while ETT is more suitable for maintaining subtree information. For example, ETT can maintain subtree minimum values while LCT cannot.
ETT can be maintained using any data structure, as long as the data structure supports the corresponding sequence interval operations and meets the complexity requirements. Generally, balanced binary search trees such as Splay or Treap are used to maintain the sequence, and these data structures maintain interval operations in \(O(\log n)\) time, thus dynamic tree operations can also be maintained in \(O(\log n)\) time. If multi-way balanced search trees like B-trees are used to maintain interval operations, even better complexity can be achieved.
In fact, ETT can be understood as an idea: by maintaining a certain sequence that corresponds one-to-one with the original tree, the purpose of maintaining the original tree is achieved. This article only introduces some feasible implementations and applications of this idea.
Euler Tour Representation of a Tree
If each tree edge is regarded as two directed edges, then a tree can be represented as an Euler tour of a directed graph, called the Euler tour representation (ETR) of the tree.
The sequence to be maintained later is actually a variant of ETR, where vertices in the tree are treated as self-loops and added to the ETR. However, since the original paper did not give it a new name, it is still called ETR.
The Euler tour representation of 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, each time a node or a directed edge is visited, it is appended to the end of \(\operatorname{ETR}(T)\), thus obtaining \(\operatorname{ETR}(T)\).
If \(T\) contains \(n\) nodes, then it contains \(2n - 2\) directed edges. During DFS, each node and each directed edge is visited exactly once, so the length of \(\operatorname{ETR}(T)\) is \(3n - 2\).
Treating node \(u\) as a self-loop, \(\operatorname{ETR}(T)\) can be seen as an Euler tour in a directed graph. The Euler tour can be broken at some point, viewed as a chain formed by connecting edges end-to-end; such a chain can be reconnected at the break point to restore the Euler tour; also, new edges can be added to join two such chains into a new Euler tour.
In the following, unless otherwise specified, the maintained sequence is the Euler tour representation of the tree.
Basic Operations of ETT
The following three operations are considered basic operations of ETT, and each can be transformed into a constant number of sequence operations. Therefore, the complexity of these three operations is of the same order as the sequence operations.
Here, only one feasible implementation is given. As long as the modified corresponding sequence can be constructed using a constant number of sequence operations, it is acceptable.
MakeRoot(u)
This is the rerooting operation. In ETT, the rerooting operation is transformed into 1 sequence split operation and 1 sequence merge operation, which can also be understood as 1 interval rotation operation.
Let the tree containing node \(u\) be \(T\), with current root \(r\), and now we want to change the root to \(u\). The sequence corresponding to tree \(T\) is \(L\). Split \(L\) at \((u, u)\) into sequences \(L^1\) and \(L^2\), where the former contains elements before \((u, u)\) in \(L\) and \((u, u)\) itself, and the latter contains the remaining elements. Then merging \(L^2\) and \(L^1\) in order yields the sequence corresponding to the tree after rerooting.
This can be understood as rotating an Euler tour. An Euler tour is a cycle, and rotation does not change the structure of the Euler tour, i.e., does not change the tree structure, but only rotates node \(u\) to the root position.
Insert(u, v)
This is the edge addition operation. In ETT, the edge addition operation is transformed into 2 sequence split operations and 5 sequence merge operations.
Let the tree containing node \(u\) be \(T_1\), and the tree containing node \(v\) be \(T_2\). After adding the edge, the two trees merge into one tree \(T\). The sequence corresponding to tree \(T_1\) is \(L_1\), and the sequence corresponding to tree \(T_2\) is \(L_2\).
Split \(L_1\) at \((u, u)\) into sequences \(L_1^1\) and \(L_1^2\), where the former contains elements before \((u, u)\) in \(L_1\) and \((u, u)\) itself, and the latter contains the remaining elements. Similarly, split \(L_2\) at \((v, v)\) into sequences \(L_2^1\) and \(L_2^2\). Then merging \(L_1^2, L_1^1, [(u, v)], L_2^2, L_2^1, [(v, u)]\) in order yields the sequence \(L\) corresponding to tree \(T\).
This can be understood as two rerooting operations, then breaking the two Euler tours at the current root positions, and using the two newly added directed edges to join the two Euler tours into a new Euler tour.
Delete(u, v)
This is the edge deletion operation. In ETT, the edge deletion operation is transformed into 4 sequence split operations and 1 sequence merge operation.
Let the tree containing edges \((u, v)\) and \((v, u)\) be \(T\), with corresponding sequence \(L\). After deletion, \(T\) splits into two trees.
Split \(L\) into \(L_1, [(u, v)], L_2, [(v, u)], L_3\). The sequences corresponding to the two trees formed by deletion are \(L_2\) and \(L_1, L_3\), respectively. Note that in sequence \(L\), \([(u, v)]\) might appear after \([(v, u)]\). In that case, we can first swap the values of \(u\) and \(v\) and then perform the operation.
This can be understood as breaking an Euler tour at two directed edges to form two chains, then each chain connects its own ends to form two new Euler tours.
Implementation
The following uses non-rotating Treap as an example to introduce the implementation of ETT. Readers are expected to be familiar with using non-rotating Treap to maintain interval operations.
Split and Merge are basic operations of non-rotating Treap and will not be elaborated here.
SplitUp2(u)
Assume the sequence containing \(u\) is \(L\). Split \(L\) at \(u\) into sequences \(L^1\) and \(L^2\), where the former contains elements before \(u\) in \(L\) and \(u\) itself, and the latter contains the remaining elements.
If each node of the Treap additionally maintains its parent, then the position of a Treap node's corresponding element in the sequence can be computed in \(O(\log n)\) time. Then splitting based on position can achieve the above functionality.
Alternatively, splitting from bottom up can also achieve the above functionality, which is more efficient compared to the above method. Specifically, while traversing from the node corresponding to \(u\) up to the root, the binary search tree property can determine whether each node is before or after \(u\) in \(L\). Based on this, the position of \(u\) in the sequence can be computed, and each node can be assigned to the appropriate tree after splitting.
/* * 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. */staticstd::pair<Node*,Node*>SplitUp2(Node*p){Node*a=nullptr,*b=nullptr;b=p->right_;if(b)b->parent_=nullptr;p->right_=nullptr;boolis_p_left_child_of_parent=false;boolis_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)
Assume the sequence containing \(u\) is \(L\). Split \(L\) at \(u\) into sequences \(L^1\), \(u\), and \(L^2\), where the former contains elements before \(u\) in \(L\), and the latter contains the remaining elements.
This can be achieved by slightly modifying SplitUp2.
MakeRoot(u)
Based on SplitUp2 and Merge, it is straightforward.
Nodes \(u\) and \(v\) are connected if and only if they belong to the same tree \(T\), i.e., \((u, u)\) and \((v, v)\) belong to \(\operatorname{ETR}(T)\). This can be determined by checking whether the Treap nodes corresponding to \(u\) and \(v\) belong to the same Treap root.
#include<cassert>#include<cstdint>#include<functional>#include<iostream>#include<map>#include<random>#include<sstream>usingi64=int64_t;usingu64=uint64_t;voidsolve_case(intCase);intmain(intargc,char*argv[]){std::ios::sync_with_stdio(false),std::cin.tie(nullptr);intT=1;// std::cin >> T;for(intt=1;t<=T;++t){solve_case(t);}return0;}/** * 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 */classDynamicForest{private:staticstd::mt19937rng_;structNode{intsize_;intpriority_;Node*left_;Node*right_;Node*parent_;intfrom_;intto_;Node(intfrom,intto):size_(1),priority_(rng_()),left_(nullptr),right_(nullptr),parent_(nullptr),from_(from),to_(to){}voidMaintain(){size_=1;if(left_){size_+=left_->size_;left_->parent_=this;}if(right_){size_+=right_->size_;right_->parent_=this;}}};staticintGetSize(Node*p){returnp==nullptr?0:p->size_;}staticNode*FindRoot(Node*p){if(!p)returnnullptr;while(p->parent_!=nullptr)p=p->parent_;returnp;}staticstd::stringto_string(Node*p){std::stringstreamss;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";returnss.str();}Node*AllocateNode(intu,intv){Node*p=newNode(u,v);returnp;}voidFreeNode(Node*&p){if(p){deletep;p=nullptr;}}/* * Dynamic Sequence Maintained using Treap. */classTreap{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. */staticNode*Merge(Node*a,Node*b){if(a==nullptr)returnb;if(b==nullptr)returna;if(a->priority_<b->priority_){a->right_=Merge(a->right_,b);a->Maintain();returna;}else{b->left_=Merge(a,b->left_);b->Maintain();returnb;}}/** * 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. */staticintGetPosition(Node*p){assert(p!=nullptr);intposition=GetSize(p->left_)+1;while(p){if(p->parent_&&p==p->parent_->right_)position+=GetSize(p->parent_->left_)+1;p=p->parent_;}returnposition;}/** * Split sequence containning p into two sequences, the first one contains * the first k elements, the second one contains the remaining elements. */staticstd::pair<Node*,Node*>Split(Node*p,intk){if(!p)return{nullptr,nullptr};std::pair<Node*,Node*>result;if(GetSize(p->left_)<k){autoright_result=Split(p->right_,k-GetSize(p->left_)-1);p->right_=right_result.first;result.first=p;result.second=right_result.second;}else{autoleft_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;returnresult;}/* * 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. */staticstd::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;boolis_p_left_child_of_parent=false;boolis_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. */staticstd::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;boolis_p_left_child_of_parent=false;boolis_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(intn):n_(n),vertices_(n_),tree_edges_(n_){assert(n_>0);for(inti=0;i<n_;++i)vertices_[i]=AllocateNode(i,i);}~DynamicForest(){for(inti=0;i<n_;++i){for(autop:tree_edges_[i]){FreeNode(p.second);}}for(inti=0;i<n_;++i){FreeNode(vertices_[i]);}}voidInsert(intu,intv){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;intposition_u=Treap::GetPosition(vertex_u);intposition_v=Treap::GetPosition(vertex_v);autop1=Treap::SplitUp2(vertex_u);autop2=Treap::SplitUp2(vertex_v);autoL11=p1.first,L12=p1.second;autoL21=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);}voidDelete(intu,intv){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);intposition_uv=Treap::GetPosition(edge_uv);intposition_vu=Treap::GetPosition(edge_vu);if(position_uv>position_vu){std::swap(edge_uv,edge_vu);std::swap(position_uv,position_vu);}autop1=Treap::SplitUp3(edge_uv);autoL1=std::get<0>(p1),uv=std::get<1>(p1);assert(GetSize(L1)==position_uv-1);assert(GetSize(uv)==1);autop2=Treap::SplitUp3(edge_vu);autoL2=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);}boolIsConnected(intu,intv){Node*vertex_u=vertices_[u];Node*vertex_v=vertices_[v];returnFindRoot(vertex_u)==FindRoot(vertex_v);}std::stringto_string()const{std::stringstreamss;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(inti=0;i<n_;++i){if(vertices_[i]->parent_==nullptr){ss<<" Component [";dfs(vertices_[i]);ss<<"]\n";}}for(inti=0;i<n_;++i){for(autop:tree_edges_[i]){if(p.second->parent_==nullptr){ss<<" Component [";dfs(p.second);ss<<"]\n";}}}ss<<"]\n\n";returnss.str();}private:intn_;std::vector<Node*>vertices_;std::vector<std::map<int,Node*>>tree_edges_;};std::mt19937DynamicForest::rng_(std::random_device{}());voidsolve_case(intCase){intn,m;std::cin>>n>>m;DynamicForestt(n+1);std::stringop;intu,v;for(inti=1;i<=m;++i){std::cin>>op;std::cin>>u>>v;if(op[0]=='Q'){std::cout<<(t.IsConnected(u,v)?"Yes":"No")<<"\n";}elseif(op[0]=='C'){t.Insert(u,v);}elseif(op[0]=='D'){t.Delete(u,v);}}}
Maintaining Subtree Information
The following uses subtree node count as an example.
For each element in \(\operatorname{ETR}(T)\), if the element corresponds to a node in the tree, assign it a weight of \(1\); if it corresponds to an edge in the tree, assign it a weight of \(0\). Now the node count of tree \(T\) can be seen as the sum of weights of elements in \(\operatorname{ETR}(T)\). It only requires maintaining the sequence weight sum to achieve maintaining subtree node count. Maintaining sequence weight sum is a classic operation of non-rotating Treap.
Similarly, operations like subtree minimum can be transformed into classic balanced tree operations like sequence minimum and then maintained.
#include<cassert>#include<cstdint>#include<functional>#include<iostream>#include<map>#include<random>#include<sstream>usingi64=int64_t;usingu64=uint64_t;voidsolve_case(intCase);intmain(){std::ios::sync_with_stdio(false),std::cin.tie(nullptr);intT=1;// std::cin >> T;for(intt=1;t<=T;++t){solve_case(t);}return0;}/** * 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 */classDynamicForest{private:staticstd::mt19937rng_;structNode{intsize_;intpriority_;Node*left_;Node*right_;Node*parent_;intfrom_;intto_;intnum_vertex_;intnum_edge_;Node(intfrom,intto):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){}voidMaintain(){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_;}}};staticintGetSize(Node*p){returnp==nullptr?0:p->size_;}staticNode*FindRoot(Node*p){if(!p)returnnullptr;while(p->parent_!=nullptr)p=p->parent_;returnp;}staticstd::stringto_string(Node*p){std::stringstreamss;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";returnss.str();}Node*AllocateNode(intu,intv){Node*p=newNode(u,v);returnp;}voidFreeNode(Node*&p){if(p){deletep;p=nullptr;}}/* * Dynamic Sequence Maintained using Treap. */classTreap{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. */staticNode*Merge(Node*a,Node*b){if(a==nullptr)returnb;if(b==nullptr)returna;if(a->priority_<b->priority_){a->right_=Merge(a->right_,b);a->Maintain();returna;}else{b->left_=Merge(a,b->left_);b->Maintain();returnb;}}/** * 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. */staticintGetPosition(Node*p){assert(p!=nullptr);intposition=GetSize(p->left_)+1;while(p){if(p->parent_&&p==p->parent_->right_)position+=GetSize(p->parent_->left_)+1;p=p->parent_;}returnposition;}/** * Split sequence containning p into two sequences, the first one contains * the first k elements, the second one contains the remaining elements. */staticstd::pair<Node*,Node*>Split(Node*p,intk){if(!p)return{nullptr,nullptr};std::pair<Node*,Node*>result;if(GetSize(p->left_)<k){autoright_result=Split(p->right_,k-GetSize(p->left_)-1);p->right_=right_result.first;result.first=p;result.second=right_result.second;}else{autoleft_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;returnresult;}/* * 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. */staticstd::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;boolis_p_left_child_of_parent=false;boolis_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. */staticstd::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;boolis_p_left_child_of_parent=false;boolis_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(intn):n_(n),vertices_(n_),tree_edges_(n_){assert(n_>0);for(inti=0;i<n_;++i)vertices_[i]=AllocateNode(i,i);}~DynamicForest(){for(inti=0;i<n_;++i){for(autop:tree_edges_[i]){FreeNode(p.second);}}for(inti=0;i<n_;++i){FreeNode(vertices_[i]);}}voidMakeRoot(intu){Node*vertex_u=vertices_[u];intposition_u=Treap::GetPosition(vertex_u);autop1=Treap::SplitUp2(vertex_u);autoL1=p1.first,L2=p1.second;assert(GetSize(L1)==position_u);Treap::Merge(L2,L1);}voidInsert(intu,intv){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;intposition_u=Treap::GetPosition(vertex_u);intposition_v=Treap::GetPosition(vertex_v);autop1=Treap::SplitUp2(vertex_u);autop2=Treap::SplitUp2(vertex_v);autoL11=p1.first,L12=p1.second;autoL21=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);}voidDelete(intu,intv){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);intposition_uv=Treap::GetPosition(edge_uv);intposition_vu=Treap::GetPosition(edge_vu);if(position_uv>position_vu){std::swap(edge_uv,edge_vu);std::swap(position_uv,position_vu);}autop1=Treap::SplitUp3(edge_uv);autoL1=std::get<0>(p1),uv=std::get<1>(p1);assert(GetSize(L1)==position_uv-1);assert(GetSize(uv)==1);autop2=Treap::SplitUp3(edge_vu);autoL2=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);}boolIsConnected(intu,intv){Node*vertex_u=vertices_[u];Node*vertex_v=vertices_[v];returnFindRoot(vertex_u)==FindRoot(vertex_v);}intGetComponentSize(intu){Node*vertex_u=vertices_[u];Node*root_of_vertex_u=FindRoot(vertex_u);returnGetSize(root_of_vertex_u);}intGetComponentNumberOfVertex(intu){Node*vertex_u=vertices_[u];Node*root_of_vertex_u=FindRoot(vertex_u);returnroot_of_vertex_u?root_of_vertex_u->num_vertex_:0;}std::stringto_string()const{std::stringstreamss;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(inti=0;i<n_;++i){if(vertices_[i]->parent_==nullptr){ss<<" Component [";dfs(vertices_[i]);ss<<"]\n";}}for(inti=0;i<n_;++i){for(autop:tree_edges_[i]){if(p.second->parent_==nullptr){ss<<" Component [";dfs(p.second);ss<<"]\n";}}}ss<<"]\n\n";returnss.str();}private:intn_;std::vector<Node*>vertices_;std::vector<std::map<int,Node*>>tree_edges_;};std::mt19937DynamicForest::rng_(std::random_device{}());voidsolve_case(intCase){intn,q;std::cin>>n>>q;DynamicForestt(n+1);std::stringop;intu,v;for(inti=1;i<=q;++i){std::cin>>op>>u>>v;if(op[0]=='A'){t.Insert(u,v);}elseif(op[0]=='Q'){t.Delete(u,v);intans=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 bracket sequences to transform tree path information into interval information, then use data structures to maintain the sequence and thus maintain tree path information. However, this technique requires that the maintained information satisfies subtractability.
The sequence operations corresponding to the dynamic tree operations introduced earlier may move right parentheses before left parentheses in the bracket sequence. Therefore, when maintaining information like tree path node sum, extra care is needed to ensure that operations do not change the order of corresponding left and right parentheses. This may require rethinking the sequence operations corresponding to dynamic tree operations, or even rethinking what kind of DFS sequence to maintain.
Additionally, ETT has difficulty maintaining tree path modifications.
The dynamic tree operations in this problem only involve changing the parent, which can be seen as deleting an edge and adding an edge. However, this may change the order of corresponding parentheses.
Node weights can be converted to edge weights, maintaining the bracket sequence of the tree. The parent change operation can be transformed into shifting the entire subtree's corresponding bracket sequence to after the parent's left parenthesis.
/*Although block linked list implementation of ETT was mentioned earlierand might be simpler in some cases, for this problem, block linked list could be too slow and complex to implement.Therefore, this code uses FHQ Treap for implementation.*/#include<iostream>#include<vector>constexprintN=1000000;usingnamespacestd;/*FHQ TREAP*/longlongrt,tot,f[N],rnd[N],ls[N],rs[N],siz[N],tag[N],val[N],sum[N],pd[N],pds[N];voidpushup(longlongx){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];}voidlink(longlongx,longlongc,longlongy){if(c)rs[x]=y;elsels[x]=y;if(y)f[y]=x;pushup(x);}longlongnewNode(longlongx,longlongy){siz[++tot]=1;val[tot]=sum[tot]=x;pd[tot]=pds[tot]=y;rnd[tot]=rand();returntot;}voidsetTag(longlongx,longlongv){tag[x]+=v;sum[x]+=v*pds[x];val[x]+=v*pd[x];}voidpushdown(longlongx){if(ls[x])setTag(ls[x],tag[x]);if(rs[x])setTag(rs[x],tag[x]);tag[x]=0;}voidsplit(longlongnow,longlongk,longlong&x,longlong&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]);}}longlongmerge(longlongx,longlongy){if(!x||!y)returnx|y;if(rnd[x]<rnd[y]){pushdown(x);link(x,1,merge(rs[x],y));returnx;}else{pushdown(y);link(y,0,merge(x,ls[y]));returny;}}longlongrnk(longlongx){longlongc=1,ans=0;while(x){if(c)ans+=siz[ls[x]]+1;c=(rs[f[x]]==x);x=f[x];}returnans;}/*ETT*/longlongs[N],e[N];voidadd(longlongx,longlongv){longlonga,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 want to operate on.setTag(b,v);rt=merge(merge(a,b),c);}longlongquery(longlongx){longlonga,b;split(rt,rnk(s[x]),a,b);longlongans=sum[a];rt=merge(a,b);returnans;}voidchangeFa(longlongx,longlongy){longlonga,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);// Since we cannot determine which side of the bracket sequence the new parent node is on, we merge the two sides first.split(a,rnk(s[y]),a,d);rt=merge(merge(a,b),d);// Place the subtree to be operated on at the beginning of the parent's bracket sequence.}/*main function*/longlongn,m,w[N];vector<longlong>v[N];voiddfs(longlongx){rt=merge(rt,s[x]=newNode(w[x],1));for(autoto:v[x])dfs(to);rt=merge(rt,e[x]=newNode(-w[x],-1));}signedmain(){cin>>n;for(longlongi=2;i<=n;i++){longlongf;cin>>f;v[f].push_back(i);}for(longlongi=1;i<=n;i++)cin>>w[i];dfs(1);cin>>m;for(longlongi=1;i<=m;i++){charc;cin>>c;if(c=='Q'){longlongd;cin>>d;cout<<query(d)<<endl;}elseif(c=='C'){longlongx,y;cin>>x>>y;changeFa(x,y);}else{longlongp,q;cin>>p>>q;add(p,q);}}return0;}
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.