数据结构&图论：欧拉游览树

ETT可以称为欧拉游览树，它是一种和欧拉序有关的动态树（LCT是解决动态树问题的一种方案，这是另一种）

dfs序和欧拉序是把树问题转化到区间问题上然后再用数据结构去维护的利器

通过借助这两种形式能够完成子树的查询和修改，这是LCT所不能胜任的工作

所谓的ETT就是通过动态维护欧拉序来实现动态树

它能完成换父亲（Cut和Link操作）

修改子树（LCT实现不了）

查询结点到根的信息

当然它对比于LCT还是有局限性的

这些操作通过DFS序+Splay也可以完成

只不过我们通俗地把欧拉序+Splay称作ETT而已

这个代码在我交上去的时候WA了一发，printf函数在处理long long的时候一定要小心

代码细节等以后对DFS序和欧拉序了解更加充分以及对数据结构掌握的更好的时候再回过头来看

 #include<cstdio>

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,cnt,tot,m;

 int a[maxn],g[maxn];

 int lch[maxn],rch[maxn],dfn[maxn];

 int fa[maxn],size[maxn],mark[maxn];

 long long lazy[maxn],sum[maxn],val[maxn];

 int ch[maxn][];

 struct Edge

 {

     int t,next;

 }e[maxm];

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>'') {if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 void addedge(int u,int v)

 {

     cnt++;

     e[cnt].t=v;e[cnt].next=g[u];

     g[u]=cnt;

 }

 void dfs(int x)  //计算欧拉序

 {

     lch[x]=++tot;

     dfn[lch[x]]=x;

     for(int tmp=g[x];tmp;tmp=e[tmp].next)

         dfs(e[tmp].t);

     rch[x]=++tot;

     dfn[rch[x]]=-x;

 }

 void push_down(int x)

 {

     if(x&&fa[x]) push_down(fa[x]);

     if(x==||lazy[x]==) return;

     lazy[ch[x][]]+=lazy[x];

     lazy[ch[x][]]+=lazy[x];

     val[ch[x][]]+=lazy[x]*mark[ch[x][]];

     val[ch[x][]]+=lazy[x]*mark[ch[x][]];

     sum[ch[x][]]+=(long long)size[ch[x][]]*lazy[x];

     sum[ch[x][]]+=(long long)size[ch[x][]]*lazy[x];

     lazy[x]=;

 }

 int dir(int x)

 {

     return ch[fa[x]][]==x;

 }

 void push_up(int x)

 {

     sum[x]=sum[ch[x][]]+sum[ch[x][]]+val[x];

     size[x]=size[ch[x][]]+size[ch[x][]]+mark[x];

 }

 void rotate(int x,int d)

 {

     int tmp=ch[x][d^];

     ch[x][d^]=ch[tmp][d];

     if(ch[x][d^]) fa[ch[x][d^]]=x;

     fa[tmp]=fa[x];

     if(fa[x]) ch[fa[x]][dir(x)]=tmp;

     fa[x]=tmp;

     ch[tmp][d]=x;

     push_up(x);push_up(tmp);

 }

 void splay(int x,int goal)

 {

     push_down(x);

     while(fa[x]!=goal)

     {

         if(fa[fa[x]]!=goal&&dir(x)==dir(fa[x]))

             rotate(fa[fa[x]],dir(x)^);

         rotate(fa[x],dir(x)^);

     }

 }

 int find_left(int x)

 {

     splay(x,);

     x=ch[x][];

     while(ch[x][]) x=ch[x][];

     return x;

 }

 int find_right(int x)

 {

     splay(x,);

     x=ch[x][];

     while(ch[x][]) x=ch[x][];

     return x;

 }

 int build(int l,int r)

 {

     if(l>r) return ;

     int mid=(l+r)>>;

     if(mid<r)

     {

         ch[mid][]=build(mid+,r);

         fa[ch[mid][]]=mid;

     }

     if(l<mid)

     {

         ch[mid][]=build(l,mid-);

         fa[ch[mid][]]=mid;

     }

     if(dfn[mid]>) val[mid]=a[dfn[mid]];

     else val[mid]=-a[-dfn[mid]];

     if(dfn[mid]>) mark[mid]=;

     else mark[mid]=-;

     push_up(mid);

     return mid;

 }

 int main()

 {

     int x,y;

     char opt;

     n=read();

     for(int i=;i<=n;i++)

     {

         x=read();

         addedge(x,i);

     }

     dfs();

     for(int i=;i<=n;i++) a[i]=read();

     build(,tot+);

     m=read();

     while(m--)

     {

         opt=getchar();

         while(opt!='Q'&&opt!='C'&&opt!='F') opt=getchar();

         x=read();

         if(opt=='Q')

         {

             splay(lch[x],);

             printf("%lld\n",sum[ch[lch[x]][]]+val[lch[x]]);

         }

         else if(opt=='C')

         {

             y=read();

             int aa=find_left(lch[x]),bb=find_right(rch[x]);

             splay(aa,);splay(bb,aa);

             int tmp=ch[bb][];

             ch[bb][]=;

             push_up(bb);push_up(aa);

             x=find_left(rch[y]);

             splay(x,);splay(rch[y],x);

             fa[tmp]=rch[y];

             ch[rch[y]][]=tmp;

             push_up(rch[y]);push_up(x);

         }

         else

         {

             y=read();

             int aa=find_left(lch[x]),bb=find_right(rch[x]);

             splay(aa,);splay(bb,aa);

             lazy[ch[bb][]]+=y;

             val[ch[bb][]]+=y*mark[ch[bb][]];

             sum[ch[bb][]]+=(long long)size[ch[bb][]]*y;

         }

     }

     return ;

 }

巴特西

数据结构&图论：欧拉游览树

最新文章

热门文章