浅谈ETT

jerry3128 · 2021-04-26 13:12:33 · 个人记录

Euler - Tour - Tree

Video Access: https://www.bilibili.com/video/BV1Hh8qeGEgt

零. 前言

本文着重介绍几类 ETT 的实现方式与其对应的维护信息，分析其在各种信息维护上的优劣。

ETT 只是对能动态维护欧拉环游序数据结构的总称，其载体包括但不限于：平衡树、块链等数据结构。
ET 序的存储方法也分为4种情况，待会会一一讨论。
介绍的顺序后面能做得操作包含前面能做的。

首先来介绍几种基于欧拉环游序和其的省略或者类似的版本。目前笔者自己研究的独立 ETT 仅能做到自由 link-cut 维护子树信息，要求交换律与结合律。

一. DFS序

这种情况经常出现在我们的静态树剖当中，较为平凡，我们不在此详细讨论。

二. 括号序

括号序，即在 DFS 时入和出都对一个点进行记录，入为加入信息，出为删除信息，这样的性质就有：
1. 一个点的子树就是它入和出之间的区间。
2. 一个点到根的链的信息和就是它入的信息前缀和。
再用数据结构维护即可平凡地做到换父亲，子树修改，链查询。
链修改与子树查询与换根再后文提到。

三. 欧拉环游序

在括号序的基础上，每个点在它的两个直接相连的儿子之间转移时加上自己。
欧拉环游序与括号序都能唯一对应一棵树，加上维护序列的数据结构就可以维护动态树问题。

下面就来介绍几种实用的例子。

一. splay - 括号序

这是几种例子当中最好实现的一种，可以直接参见例题【BZOJ3786】星系探索，较为平凡，不过多赘述。

二. FHQ - 正反弧ETT

这种 ETT 对于生成树有十分优秀的维护复杂度。
首先考虑如何维护基础操作。
欧拉环游序：对于任意一棵树都有它的欧拉环游序，即每次到达节点都直接把这个点加入序列。如:
ETT就是基于欧拉环游序的数据结构，用splay对序列的操作来维护欧拉环游序，接下来详细介绍一下它的操作。
Link操作:可以已发现新的欧拉环游序，就是将子树的欧拉环游序插入任意一个“父亲节点的编号”的后面，由于返回的时候又得访问一次“父亲节点的编号”,所以要再加一个“父亲节点的编号”。
Cut操作:直接将子树“挖”出来就行了。并删除一次访问“父亲节点的编号”。
askroot操作：序列的第一个数字就是根。
在 O(\log n) 的时间内能够完成 link,cut 与 makeroot 操作（区间平移与翻转，FHQ 是 ETT 的维护载体，正反弧是记录的附加信息）。
因为其只有一颗 ETT 的独特性质， ~~它能够做许多乱搞树形态的骚操作~~ 。
关于实现就是用 FHQ 先平凡地记录欧拉环游序，再新开一个 map，如果存在再欧拉环游序上一对父子点 (x,y) 那么必然在欧拉环游序上有两个地方 x,y 相邻，记 map[x][y]=x 的后面就是 y，y 在 FHQ 上的点编号，再记一个反的，定义是一样的。
或者换根的时候再来一次全局翻转，这样就只剩下区间平移了。
每次就可以直接找到节点的在 FHQ 上信息，能快速的完成结构维护操作，而且拥有平衡树的性质。
这个数据结构在动态图的完全连通性与 Contraction-based top tree 中都发挥了重要的作用。 code

在具体实现的时候我一般省略第一个节点，以为首先其显然等于最后一个节点，然后省略后，换根可以直接看做区间平移。

三. LCT - ETT

ETT和括号序在动态情况下难以对单独找出链信息主要瓶颈在于在合理的时间复杂度以内用区间表示出一条链。
我们令一个点第一次出现的点为代表节点，只有他会存储信息。
由于平衡树的性质，我们可以在O(\log n)的时间完成区间平移，这启发我们将静态的树链剖分维护改为LCT维护。
先考虑想要得到状态，即一个实链 splay 中的所有的节点组成的链能够在ETT上被方便的表示出来。那么为了得到这个结构，我们在LCT虚实儿子变换的时候将操作映射到 ETT 上。若y即将成为x的实儿子，那么我们就在ETT对应的将y所在实链的所有点的子树区间平移到x的右边，与x相邻，保证操作前后合法，那么完成操作后，y到根的代表节点全都在整个ETT的最左侧。
换根也比较平凡，找到x的代表节点，access 它，然后 [1,rk_{x}],[rk_{x}+1,last] 分别翻转，至于正反翻反了的可以直接标记解决。
那么它就可以维护一颗动态树的链和子树的查询与修改操作了。
子树大小可以有LCT直接维护，故只需记录代表节点，且欧拉环游序，括号序，DFS序，均可以实现。 LCT - ETT

例题

题单版本
【BZOJ3786】星系探索
【BJOI2014】大融合
【模板】动态图完全连通性
【Ynoi2012】梦断 SCOI2017
【模板】Euler - Tour - Tree
【CF414E】 Mashmokh's Designed Problem

【Ynoi2012】梦断 SCOI2017

题目大意：

有一颗静态树，一共有 30 种颜色，每次会单点或者同色块修改颜色。
询问：
- 某个节点的颜色。
- 这个节点的同色块的大小。
- 这个节点同色块的深度最大值和最小值。

题解：splay & 括号序。

我们考虑对于每一个节点维护每一种不同于自己颜色的儿子的 ETT ，如果一个节点的颜色与父亲相同，那么这个节点应与父亲在同一颗 ETT 当中。即我们用 ETT 森林维护每一个同色连通块。如果两个连通块有相同的颜色和父亲并且颜色不同于父亲，那么显然他们可以简单地收尾相接将二者合并。并维护出链接异色节点的父子边，把标记打在父亲上。
那么找到一个块的信息就是在 ETT 上直接 splay 后得到的信息。异色块的信息都被专门维护的异色边隔离开。一个 ETT 上的根就是一个同色连通块的根。
考虑操作一，如果对单点颜色进行修改。那么我们考虑信息变更的部分：
- 它与父亲的关系：可能从父亲的 ETT 中被挖出来，也可能被放入父亲的 ETT 中。
- 它与儿子的关系：当前 ETT 子树区间的所有儿子都会变成异色的，同时可能会有本来异色的儿子变为同色的。因为在刚刚我们将颜色相同且父亲相同的儿子的 ETT 收尾相接，所以可以直接把整个 splay 挂在当前的点的括号序之间。
考虑操作二，对块颜色进行修改，那么就是整个 ETT 被带着跑。考虑信息改变部分。
- 它的块根与父亲的关系：可能整颗 ETT 被放入块根父亲的括号序之间，或者什么也没有。
- 整个块向外连出的异色边：有可能修改的目标颜色会涉及多个异色边。
前者很好维护，后者我们看所谓的“异色边”的本质。先把“异色边”新定义放这：每个节点向某个异色亲儿子点集的连边。（一个集合算一条）
因为我们将颜色、父亲相同的块根的 ETT 相接，因此可以直接集合操作。即异色边的本质应该是：每个节点的亲儿子当中不同于当前节点颜色的种数，处于 O(nc)，再看异色边的变化，每次操作一最多增加 2 的异色边，分别为操作节点的父亲与操作节点当前同色的儿子。操作二会遍历一颗 ETT 来找到将删除的异色边，因为用了平衡树作为维护 ETT 的东西，所以找到一个节点的复杂度是均摊 O(\log n) 的，每个节点对于一种颜色最多只有一条异色边。所以复杂度是均摊 O(\log n) 减少一条“异色边”。全局均摊复杂度是完全能够接受的。

//ayame保佑，夸哥保佑，狗妈保佑，MDR保佑，锉刀怪保佑，M99保佑，克爹保佑
#include<bits/stdc++.h>
using namespace std;
int p1=1000000,p2=0;
char buf[1000005],wb[1000005];
int gc() {
    if(p1>=1000000)fread(buf,1,1000000,stdin),p1=0;
    return buf[p1++];
}
#define gc getchar
#define Loli true
#define Kon xor true
long long getint() {
    long long ret=0,flag=1;
    char c=gc();
    while(c<'0'||c>'9') {
        if(c=='-')flag=-1;
        c=gc();
    }
    while(c<='9'&&c>='0') {
        ret=(ret<<3)+(ret<<1)+c-'0';
        c=gc();
    }
    return ret*flag;
}
void pc(char x) {
    if(p2>=1000000)fwrite(wb,1,1000000,stdout),p2=0;
    wb[p2++]=x;
}
void wrt(long long x) {
    if(x<0)pc('-'),x=-x;
    int c[24]= {0};
    if(!x)return pc('0'),void();
    while(x)c[++c[0]]=x%10,x/=10;
    while(c[0])pc(c[c[0]--]+'0');
}
int n,m,a[100005];
int fa[100005],dep[100005];
int o[100005][31],prt[20][100005];
namespace ETT {
    struct node {
        int ch[2],fa,pre,suf;
        int vl,sz,dep,mx,mi,etag,stag;
        int col,ctag;
    } v[200005];
    void push_down(int rt) {
        if(v[rt].ctag) {
            if(v[rt].ch[0])v[v[rt].ch[0]].ctag=v[v[rt].ch[0]].col=v[rt].ctag;
            if(v[rt].ch[1])v[v[rt].ch[1]].ctag=v[v[rt].ch[1]].col=v[rt].ctag;
            v[rt].ctag=0;
        }
    }
    void push_up(int rt) {
        v[rt].pre=v[rt].suf=rt;
        v[rt].mx=v[rt].mi=v[rt].dep;
        if(v[rt].ch[0])v[rt].pre=v[v[rt].ch[0]].pre,v[rt].mx=max(v[rt].mx,v[v[rt].ch[0]].mx),v[rt].mi=min(v[rt].mi,v[v[rt].ch[0]].mi);
        if(v[rt].ch[1])v[rt].suf=v[v[rt].ch[1]].suf,v[rt].mx=max(v[rt].mx,v[v[rt].ch[1]].mx),v[rt].mi=min(v[rt].mi,v[v[rt].ch[1]].mi);
        v[rt].stag=v[rt].etag|v[v[rt].ch[0]].stag|v[v[rt].ch[1]].stag;
        v[rt].sz=v[v[rt].ch[0]].sz+v[rt].vl+v[v[rt].ch[1]].sz;
    }
    void rot(int x) {
        int p=v[x].fa,g=v[p].fa;
        bool d=v[p].ch[1]==x;
        if(g)v[g].ch[v[g].ch[1]==p]=x;
        v[p].ch[d]=v[x].ch[d^1];
        v[v[x].ch[d^1]].fa=p;
        v[x].ch[d^1]=p;
        v[x].fa=g,v[p].fa=x;
        push_up(p),push_up(x);
    }
    void pre_push_down(int rt) {
        if(v[rt].fa)pre_push_down(v[rt].fa);
        push_down(rt);
    }
    void splay(int x,int f=0) {
        if(!x)return;
        pre_push_down(x);
        while(v[x].fa!=f) {
            int p=v[x].fa,g=v[p].fa;
            if(g!=f)rot(v[g].ch[0]==p^v[p].ch[0]==x?x:p);
            rot(x);
        }
    }
    void init() {
        for(int i=1; i<=n; i++) {
            v[i<<1].vl=1,v[i<<1].ch[1]=i<<1|1,v[i<<1|1].fa=i<<1,v[i<<1].col=a[i];
            v[i<<1].dep=v[i<<1|1].dep=dep[i],push_up(i<<1|1),push_up(i<<1);
        }
    }
    int merge_bro(int x,int y) {
        if(!x||!y)return x|y;
        splay(x),splay(y);
        int d=v[x].suf;
        splay(d),v[d].ch[1]=y,v[y].fa=d,push_up(d);
        return x;
    }
    void merge_prt(int x,int y) {
        splay(x<<1),splay(v[v[x<<1].ch[1]].pre,x<<1),splay(y);
        v[v[x<<1].ch[1]].ch[0]=y,v[y].fa=v[x<<1].ch[1],push_up(v[x<<1].ch[1]),push_up(x<<1);
    }
    int ask(int x) {
        if(x==0)return x;
        return splay(x),v[x].pre;
    }
    void dfs(int x,int c,vector<int>&vec) {
        push_down(x);
        if(v[x].etag>>c&1)vec.push_back(x>>1),v[x].etag^=1<<c;
        if(v[v[x].ch[0]].stag>>c&1)dfs(v[x].ch[0],c,vec);
        if(v[v[x].ch[1]].stag>>c&1)dfs(v[x].ch[1],c,vec);
        push_up(x);
    }
}
void ask(int x) {
    int p=x;
    for(int i=19; i>=0; i--)if(ETT::ask(p<<1)==ETT::ask(prt[i][p]<<1))p=prt[i][p];
    ETT::splay(p<<1),ETT::splay(p<<1|1,p<<1);
    int sz=ETT::v[ETT::v[p<<1|1].ch[0]].sz+1,len=max(ETT::v[ETT::v[p<<1|1].ch[0]].mx-dep[p],0)+1;
    wrt(ETT::v[p<<1].col),pc(' '),wrt(sz),pc(' '),wrt(len),pc('\n');
}
void paint_point(int x,int gc) {
    int p=x;
    for(int i=19; i>=0; i--)if(ETT::ask(p<<1)==ETT::ask(prt[i][p]<<1))p=prt[i][p];
    ETT::splay(x<<1),ETT::splay(x<<1|1,x<<1);
    int l=ETT::v[x<<1].ch[0],r=ETT::v[x<<1|1].ch[1],col=ETT::v[x<<1].col;
    ETT::v[l].fa=0,ETT::v[r].fa=0,ETT::v[x<<1].ch[0]=0,ETT::v[x<<1|1].ch[1]=0;
    ETT::push_up(x<<1|1),ETT::push_up(x<<1);

    if(fa[x]) {
        int tmp=ETT::merge_bro(l,r);
        o[fa[p]][col]=tmp;
        ETT::splay(fa[p]<<1);
        if(!o[fa[p]][col])ETT::v[fa[p]<<1].etag^=1<<col;
        ETT::push_up(fa[p]<<1);
    } else ETT::merge_bro(l,r);

    if(ETT::v[x<<1|1].ch[0]) {
        int d=ETT::v[x<<1|1].ch[0];
        ETT::v[d].fa=0,ETT::v[x<<1|1].ch[0]=0;
        ETT::push_up(x<<1|1),ETT::push_up(x<<1);
        o[x][col]=d,ETT::v[x<<1].etag|=1<<col,ETT::push_up(x<<1);
    }

    ETT::v[x<<1].col=ETT::v[x<<1|1].col=gc;

    if(o[x][gc]) {
        int d=o[x][gc];
        o[x][gc]=0,ETT::splay(d),ETT::v[x<<1|1].ch[0]=d,ETT::v[d].fa=x<<1|1;
        ETT::v[x<<1].etag^=1<<gc,ETT::push_up(x<<1|1),ETT::push_up(x<<1);
    }

    if(fa[x]) {
        ETT::splay(fa[x]<<1);
        if(gc!=ETT::v[fa[x]<<1].col) {
            o[fa[x]][gc]=ETT::merge_bro(o[fa[x]][gc],x<<1);
            ETT::splay(fa[x]<<1);
            ETT::v[fa[x]<<1].etag|=1<<gc;
            ETT::push_up(fa[x]<<1);
        } else ETT::merge_prt(fa[x],x<<1);
    }
}
void paint_block(int x,int gc) {
    for(int i=19; i>=0; i--)if(ETT::ask(x<<1)==ETT::ask(prt[i][x]<<1))x=prt[i][x];
    ETT::splay(x<<1),ETT::splay(x<<1|1,x<<1);
    int l=ETT::v[x<<1].ch[0],r=ETT::v[x<<1|1].ch[1],col=ETT::v[x<<1].col;
    ETT::v[l].fa=0,ETT::v[r].fa=0,ETT::v[x<<1].ch[0]=0,ETT::v[x<<1|1].ch[1]=0;
    ETT::push_up(x<<1|1),ETT::push_up(x<<1);

    if(fa[x]) {
        o[fa[x]][col]=ETT::merge_bro(l,r);
        ETT::splay(fa[x]<<1);
        if(!o[fa[x]][col])ETT::v[fa[x]<<1].etag^=1<<col;
        ETT::push_up(fa[x]<<1);
    } else ETT::merge_bro(l,r);

    ETT::v[x<<1].col=ETT::v[x<<1].ctag=gc;

    vector<int> vec;
    ETT::dfs(x<<1,gc,vec);
    for(int w:vec)ETT::merge_prt(w,o[w][gc]),o[w][gc]=0;

    if(fa[x]) {
        ETT::splay(fa[x]<<1);
        if(gc!=ETT::v[fa[x]<<1].col) {
            o[fa[x]][gc]=ETT::merge_bro(o[fa[x]][gc],x<<1);
            ETT::splay(fa[x]<<1);
            ETT::v[fa[x]<<1].etag|=1<<gc;
            ETT::push_up(fa[x]<<1);
        } else ETT::merge_prt(fa[x],x<<1);
    }
}
int main() {
    n=getint();
    for(int i=1; i<=n; i++)prt[0][i]=fa[i]=getint(),dep[i]=dep[fa[i]]+1;
    for(int j=1; j<20; j++)
        for(int i=1; i<=n; i++)prt[j][i]=prt[j-1][prt[j-1][i]];
    for(int i=1; i<=n; i++)a[i]=getint();
    ETT::init(),m=getint();
    for(int i=n; i>=2; i--) {
        if(a[fa[i]]==a[i])ETT::merge_prt(fa[i],i<<1);
        else o[fa[i]][a[i]]=ETT::merge_bro(o[fa[i]][a[i]],i<<1),ETT::splay(fa[i]<<1),ETT::v[fa[i]<<1].etag|=1<<a[i],ETT::push_up(fa[i]<<1);
    }
    for(int i=1; i<=m; i++) {
        int opt=getint();
        if(opt==1) {
            int x=getint(),c=getint();
            paint_point(x,c);
        }
        if(opt==2) {
            int x=getint(),c=getint();
            paint_block(x,c);
        }
        if(opt==3)ask(getint());
    }
    fwrite(wb,1,p2,stdout);
    return Loli Kon;
}

动态图的完全连通性与此类似，采用刚刚找边的均摊思想，但对 link - cut 的要求相对更强，用正反弧 ETT，和 HDLT 的分层图算法维护。