Euler Tour Tree(欧拉游览树,欧拉回路树,后文简称 ETT)是一种可以解决 动态树 问题的数据结构。ETT 将动态树的操作转换成了其 DFS 序列上的区间操作,再用其他数据结构来维护序列的区间操作,从而维护动态树的操作。例如,ETT 将动态树的加边操作转换成了多个序列拆分操作和序列合并操作,如果能维护序列拆分操作和序列合并操作,就能维护动态树的加边操作。
LCT 也是一种可以解决动态树问题的数据结构,相比 ETT 而言 LCT 会更加常见。LCT 其实更适用于维护树链的信息,而 ETT 更加适用于维护 子树 的信息。例如,ETT 可以维护子树最小值而 LCT 不能。
ETT 可以使用任意数据结构维护,只需要该数据结构支持对应的序列区间操作,以及在复杂度上满足要求。一般情况下会使用例如 Splay,Treap 等平衡二叉搜索树来维护序列,而这些数据结构维护区间操作的复杂度均为 ,由此也可以在 的时间内维护动态树的操作。如果使用多叉平衡搜索树例如 B 树来维护区间操作,也可以做到更优的复杂度。
其实 ETT 可以理解为一种思想,就是通过维护某种和原树一一对应的序列,从而达到维护原树的目的,本文介绍的只是这个思想的一些可行的实现和应用。
树的欧拉回路表示
如果把一条树边看成两条有向边的话,那么就可以把一棵树表示成一个有向图的欧拉回路,称为树的欧拉回路表示(Euler tour representation,ETR)。
/* * 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};}
#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);}}}
#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";}}}
/*虽然上文提到过块状链表实现 ETT在某些情况下可能较简单,但对于此题块状链表复杂度有可能无法通过而且实现较繁琐,所以这份代码采用FHQ Treap 实现。*/#include<iostream>#include<vector>#define N 1000000#define int long longusingnamespacestd;/*FHQ TREAP*/intrt,tot,f[N],rnd[N],ls[N],rs[N],siz[N],tag[N],val[N],sum[N],pd[N],pds[N];voidpushup(intx){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(intx,intc,inty){if(c)rs[x]=y;elsels[x]=y;if(y)f[y]=x;pushup(x);}intnewNode(intx,inty){siz[++tot]=1;val[tot]=sum[tot]=x;pd[tot]=pds[tot]=y;rnd[tot]=rand();returntot;}voidsetTag(intx,intv){tag[x]+=v;sum[x]+=v*pds[x];val[x]+=v*pd[x];}voidpushdown(intx){if(ls[x])setTag(ls[x],tag[x]);if(rs[x])setTag(rs[x],tag[x]);tag[x]=0;}voidsplit(intnow,intk,int&x,int&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]);}}intmerge(intx,inty){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;}}intrnk(intx){intc=1,ans=0;while(x){if(c)ans+=siz[ls[x]]+1;c=(rs[f[x]]==x);x=f[x];}returnans;}/*ETT*/ints[N],e[N];voidadd(intx,intv){inta,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);}intquery(intx){inta,b;split(rt,rnk(s[x]),a,b);intans=sum[a];rt=merge(a,b);returnans;}voidchangeFa(intx,inty){inta,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*/intn,m,w[N];vector<int>v[N];voiddfs(intx){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(inti=2;i<=n;i++){intf;cin>>f;v[f].push_back(i);}for(inti=1;i<=n;i++)cin>>w[i];dfs(1);cin>>m;for(inti=1;i<=m;i++){charc;cin>>c;if(c=='Q'){intd;cin>>d;cout<<query(d)<<endl;}elseif(c=='C'){intx,y;cin>>x>>y;changeFa(x,y);}else{intp,q;cin>>p>>q;add(p,q);}}return0;}
参考资料
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.