An Euler tour tree (ETT) is a data structure for dynamic tree problems. It turns each operation on a dynamic tree into range operations on a DFS sequence of the tree, and leaves those to another data structure that maintains the sequence. Adding an edge, for example, becomes a few splits and merges of sequences, so a structure that can split and merge sequences can add edges to a dynamic tree.
The LCT is another data structure for dynamic tree problems, and the more common of the two. An LCT is really better suited to information about tree paths, and an ETT to information about subtrees. For example, an ETT can maintain subtree minima and an LCT cannot.
Any data structure can sit underneath an ETT, as long as it supports the required range operations on a sequence within the required complexity. The usual choice is a balanced binary search tree such as a splay tree or a treap. These perform range operations in \(O(\log n)\), so the dynamic tree operations take \(O(\log n)\) time as well. With a multiway balanced search tree such as a B-tree, the complexity can be improved further.
An ETT is best seen as an idea: maintain a sequence that is in one-to-one correspondence with the original tree, and you maintain the tree. This article presents only some workable implementations and applications of that idea.
Euler tour representation of a tree
If each tree edge is regarded as two directed edges, a tree can be represented as an Eulerian circuit of a directed graph. This is called the Euler tour representation (ETR) of the tree.
The sequence maintained below is actually a variant of the ETR: the nodes of the tree are treated as self-loops and put into it as well. The authors of the original paper gave the variant no name of its own, so we call it the ETR too.
The following algorithm computes the Euler tour representation of a tree \(T\):
\[
\begin{array}{ll}
1 & \textbf{Input. } \text{A rooted tree }T\\
2 & \textbf{Output. } \text{The dfs sequence of rooted tree }T\\
3 & \operatorname{ET}(u)\\
4 & \qquad \text{visit vertex }u\\
5 & \qquad \text{for all children } v \text{ of } u\\
6 & \qquad \qquad \text{visit directed edge } u \to v\\
7 & \qquad \qquad \operatorname{ET}(v)\\
8 & \qquad \qquad \text{visit directed edge } v \to u\\
\end{array}
\]
The Euler tour representation \(\operatorname{ETR}(T)\) of \(T\) starts out empty. Whenever the DFS visits a node or a directed edge, append it to the end of \(\operatorname{ETR}(T)\). When the DFS ends, the representation is complete.
If \(T\) has \(n\) nodes, it has \(2n - 2\) directed edges. The DFS visits every node and every directed edge exactly once, so \(\operatorname{ETR}(T)\) has length \(3n - 2\).
Treat each node \(u\) as a self-loop. Then \(\operatorname{ETR}(T)\) is an Eulerian circuit of a directed graph. The circuit can be cut open at any point, which leaves a path of edges joined head to tail. Such a path can be glued back together at the cut to recover the circuit, and two such paths can be spliced into a new Eulerian circuit by adding a few edges.
Unless stated otherwise, the sequence maintained in the rest of this article is the Euler tour representation of the tree.
Basic operations of an ETT
The following 3 operations are the basic operations of an ETT. Each reduces to a constant number of sequence operations, so its complexity is of the same order as that of a sequence operation.
What is given here is only one possible implementation. Any way of assembling the sequence of the modified tree from a constant number of sequence operations will do.
MakeRoot(u)
This is the rerooting operation. In an ETT it becomes 1 split and 1 merge of sequences, or, seen another way, 1 range shift.
Let \(T\) be the tree containing node \(u\) and \(r\) its current root; we want to make \(u\) the root. Let \(L\) be the sequence of \(T\). Split \(L\) at \((u, u)\) into sequences \(L^1\) and \(L^2\): the first contains \((u, u)\) and the elements of \(L\) before it, the second contains the rest. Merging \(L^2\) and \(L^1\), in that order, gives the sequence of the rerooted tree.
Think of this as rotating an Eulerian circuit. The circuit is a cycle, so rotating it does not change its structure, and hence does not change the structure of the tree either: it only rotates node \(u\) into the root position.
Insert(u, v)
This operation adds an edge. In an ETT it becomes 2 splits and 5 merges of sequences.
Let \(T_1\) be the tree containing node \(u\) and \(T_2\) the tree containing node \(v\); adding the edge merges them into one tree \(T\). Let \(L_1\) be the sequence of \(T_1\) and \(L_2\) the sequence of \(T_2\).
Split \(L_1\) at \((u, u)\) into sequences \(L_1^1\) and \(L_1^2\): the first contains \((u, u)\) and the elements of \(L_1\) before it, the second contains the rest. Split \(L_2\) at \((v, v)\) into \(L_2^1\) and \(L_2^2\) in the same way. Merging \(L_1^2, L_1^1, [(u, v)], L_2^2, L_2^1, [(v, u)]\) in that order gives the sequence \(L\) of \(T\).
Think of this as two rerootings, after which the two Eulerian circuits are cut open at their current roots and spliced into a new Eulerian circuit by the two new directed edges.
Delete(u, v)
This operation deletes an edge. In an ETT it becomes 4 splits and 1 merge of sequences.
Let \(T\) be the tree containing the edges \((u, v)\) and \((v, u)\), and let \(L\) be its sequence. Deleting the edge splits \(T\) into two trees.
Split \(L\) into \(L_1, [(u, v)], L_2, [(v, u)], L_3\). The sequences of the two resulting trees are \(L_2\) and \(L_1, L_3\). Note that \([(u, v)]\) may come after \([(v, u)]\) in \(L\); in that case, swap \(u\) and \(v\) first.
Think of this as cutting an Eulerian circuit at the two directed edges, which leaves two paths; each path then closes up, head to tail, into a new Eulerian circuit.
Implementation
This section implements an ETT on top of a non-rotating treap. You should already know how a non-rotating treap handles range operations.
Split and Merge are the basic operations of a non-rotating treap, so we do not repeat them here.
SplitUp2(u)
Let \(L\) be the sequence containing \(u\). Split \(L\) at \(u\) into sequences \(L^1\) and \(L^2\): the first contains \(u\) and the elements of \(L\) before it, the second contains the rest.
If every treap node also stores its parent, the position in the sequence of the element that a treap node represents can be computed in \(O(\log n)\) time. Calling Split with that position then does the job.
The split can also be done bottom-up, which is more efficient. Climb from the node of \(u\) to the root. By the binary search tree property, we can tell for each node on the way whether it comes before or after \(u\) in \(L\). That is enough to compute the position of \(u\) in the sequence, and also to decide which of the two resulting trees each node belongs to.
/* * Bottom up split treap p into 2 treaps a and b. * - a: a treap containing nodes with position less than or equal to p. * - b: a treap containing nodes with position greater than p. * * In the other word, split sequence containing p into two sequences, the first * one contains elements before p and element p, the second one contains * elements after p. */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)
Let \(L\) be the sequence containing \(u\). Split \(L\) at \(u\) into sequences \(L^1\), \(u\) and \(L^2\): the first contains the elements of \(L\) before \(u\), the last contains the rest.
Nodes \(u\) and \(v\) are connected if and only if they belong to the same tree \(T\), that is, if \((u, u)\) and \((v, v)\) both belong to \(\operatorname{ETR}(T)\). To test this, check whether the treap nodes of \(u\) and \(v\) lie in treaps with the same root.
#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, concatenating 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 1-based index of p inside the sequence * 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 containing 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 position greater than p. * * In the other word, split sequence containing p into two sequences, the * first one contains elements before p and element p, the second one * contains elements after p. */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 containing p into three sequences, the * first one contains elements before p, the second one contains element p, * the third one contains elements after p. */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
We take the number of nodes in a subtree as the example.
Give every element of \(\operatorname{ETR}(T)\) a weight: \(1\) if it corresponds to a node of the tree, \(0\) if it corresponds to an edge. The number of nodes of \(T\) is then the sum of the weights of the elements of \(\operatorname{ETR}(T)\), so maintaining the sum of weights over a sequence is all it takes to maintain subtree sizes. And that is a classic operation on a non-rotating treap.
Similarly, operations such as subtree minimum reduce to classic balanced tree operations such as the minimum of a sequence.
#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, concatenating 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 1-based index of p inside the sequence * 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 containing 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 position greater than p. * * In the other word, split sequence containing p into two sequences, the * first one contains elements before p and element p, the second one * contains elements after p. */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 containing p into three sequences, the * first one contains elements before p, the second one contains element p, * the third one contains elements after p. */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 path information
A fairly common trick uses the properties of the bracket sequence to turn path information into range information; a data structure that maintains the sequence then maintains the path information. But the trick requires the information to be subtractable.
The sequence operations given above for the dynamic tree operations may move a closing bracket of the bracket sequence in front of its opening bracket. So maintaining something like the sum of vertex weights on a path takes extra care: no operation may change the order of a matching pair of brackets. This may mean rethinking which sequence operations implement the dynamic tree operations, or even which DFS order to maintain.
Path updates, moreover, are hard to support with an ETT.
The only dynamic tree operation in this problem is changing a node's parent. It can be seen as deleting an edge and then adding one, but done that way it may change the order of matching brackets.
Instead, turn the vertex weights into edge weights and maintain the bracket sequence of the tree. Changing a parent then becomes shifting the bracket sequence of the whole subtree to just after the opening bracket of its new parent.
/*The text above mentioned that implementing an ETT with an unrolled linked listcan be simpler in some cases. For this problem, though, it may be too slow to pass and is tedious to write, so this code usesan FHQ Treap.*/#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 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);// The new parent may lie on either side in the bracket sequence, so merge the two sides first.split(a,rnk(s[y]),a,d);rt=merge(merge(a,b),d);// Put the subtree we operate on at the very front of the parent's bracket sequence.}/*main function*/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.