题解：P3690 【模板】动态树（LCT）

· · 题解

SATT 题解。

许多人将 SATT 冠上“难理解”“代码量大”等标签。事实上，学习 LCT 以后可以无痛学习 SATT。

SATT 的优势主要是可以支持更多的子树操作，譬如臭名昭著的重工业 Sone1 如果使用 SATT 就非常容易实现。

学习 SATT 前需要了解 TopTree 理论。这一部分比较杂，这里推荐一下这篇文章。或者也可以看我的学习笔记。

接下来的图源也来自上面那篇文章，侵删。

下面部分是一些简述。若要了解完整准确的 TopTree 还请翻看上面的文章或是看看论文哥写的。

算法介绍

TopTree 理论

序列上有区间这一概念，基于区间的合并我们可以提出各种算法。于是我们对于树上也提出一个用于合并的概念。

簇：树上的一个基于边划分的连通块，满足与外界有交的点至多有两个，称为界点，界点间的路径称为簇路径。

簇的基本单位就是一条树边。

不难发现簇可以看作一个点，这样收缩以后还会是一棵树，这就是一种合并方式。接下来我们也会用点相关的描述来描述簇。

树上的合并操作不如区间上的简单，我们有两种合并方式。

rake：将度为一的簇并入兄弟的簇。

compress：将度为二的簇并入两边的簇。

这样合并以后显然还会是一棵树，簇的性质也没有消失。

类比一下线段树，将合并的过程记录下来，就可以得到一棵树，称之为 TopTree。

于是我们速通了 TopTree 理论。

实链剖分

实链剖分：由每个节点指定一个实儿子或者不指定，实儿子的父亲边称为实边，其余则称虚儿子和虚边，则连续的实边组成实链，一棵树就被划分成了不同的链。

TopTree 与实链剖分有很多不解之缘。

将每条边看出一个簇，那么所有实链上的合并都可以看作 compress 操作的结果，而虚儿子的合并可以看作 rake 操作的结果。

如果你写过动态 dp，尤其是写过全局平衡二叉树，就会发现轻子树的影响就是 rake，重链的合并就是 compress。

对于 TopTree 而言，我们可以通过自由划分实链、改变合并顺序来动态维护树结构。试问，如果可以将某个簇最后才并入整棵树的结构里，那修改还有什么困难呢？

动态维护 TopTree 的方法就是 SATT。

SATT

这一部分主要参考了 OI Wiki。

SATT 是一种基于均摊的动态 TopTree。

她是一棵三叉树，节点按照操作分为 rake 节点和 compress 节点，她们的中儿子分别挂的是 compress 节点和 rake 节点。

如果去掉中儿子，每个由 compress 节点组成的二叉树（称为 compress 树）都对应实链剖分的一条实链，中序遍历对应原实链自上而下的顺序，中儿子则表示那个节点挂的通过 rake 操作并入的虚子树。

而去掉 rake 节点的中儿子，每个 rake 节点组成的二叉树（称为 rake 树）都对应原树节点的所有虚儿子的并入操作。

然后用类似 LCT 的方式来实现这棵三叉树的操作，用类似 splay 的方式维护每棵 rake 树和 compress 树。如果您学过 LCT 可以看每个操作的省流部分。

正确性证明

这一部分过于困难了。

关于 TopTree 理论参见论文哥写的。

关于 SATT 理论请翻看 Tarjan 的原论文。

代码实现

接下来的代码示例取自 Sone1。

代码的宏定义

#define il inline
#define bl bool
#define vd void
#define ll long long
#define ull unsigned ll
#define db double
#define ldb long db
#define pii pair<int,int>
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define N 100005
#define INF 0x3f3f3f3f
#define DEBUG cerr<<"\tfurina begin:\n"
#define END cerr<<"\tyanami end.\n"

一些记号

//0:compress 1:rake
int st[N*5],top,Node;
struct node{
  int fa,son[3],lp,rp,v;bl reved;
  Dat sum[2];Tag tag[2];
  node(){fa=son[0]=son[1]=son[2]=lp=rp=v=reved=0,sum[0]=sum[1]=Dat(),tag[0]=tag[1]=Tag();}
}t[N*5];
#define isroot(x) (t[t[x].fa].son[0]^x&&t[t[x].fa].son[1]^x)
#define get(x) (t[t[x].fa].son[0]==x?0:t[t[x].fa].son[1]==x?1:2)
#define connect(x,y,w) (t[x].son[w]=y,y&&(t[y].fa=x))
il int neww(){int x=top?st[top--]:++Node;t[x]=node();return x;}

Dat 和 Tag 是封装了的，分别表示维护的信息并和标记，并重载了运算符。不影响阅读。

lp 和 rp 表示链的左右端点。

st 用于垃圾回收。

其余操作应该不难理解。

pushup

维护信息时需要分讨节点类型。

compress 节点：分别维护簇路径信息和其余节点信息。这样可以方便子树修改。

rake 节点：维护所有中儿子信息并即可。

il vd pushup(int x,bl o){
  t[x].lp=t[x].son[0]?t[t[x].son[0]].lp:x,t[x].rp=t[x].son[1]?t[t[x].son[1]].rp:x;
  if(o){//rake
    t[x].sum[1]=t[t[x].son[0]].sum[1]+(t[t[x].son[2]].sum[0]+t[t[x].son[2]].sum[1])+t[t[x].son[1]].sum[1];
    //rake tree 的 pushup 是所有点的 compress 中儿子的合并。 
  }else{//compress
    t[x].sum[0]=t[t[x].son[0]].sum[0]+Dat(1,t[x].v,t[x].v,t[x].v)+t[t[x].son[1]].sum[0];
    //compress tree 信息，直白的说就是簇路径信息。 
    t[x].sum[1]=t[t[x].son[0]].sum[1]+t[t[x].son[2]].sum[1]+t[t[x].son[1]].sum[1];
    //其余信息。 
  }
}

pushdown

与 pushup 相同，如果是 compress 节点，分讨是链修改还是子树修改下传标记。

il vd rever(int x){if(x)swap(t[x].son[0],t[x].son[1]),swap(t[x].lp,t[x].rp),t[x].reved^=1;}
il vd tager(int x,Tag tag,bl o){if(x)t[x].sum[o]=t[x].sum[o]*tag,t[x].tag[o]=t[x].tag[o]+tag,!o&&(t[x].v=tag[t[x].v]);}
il vd pushdown(int x,bl o){
  if(o){
    if(!t[x].tag[1].empty())tager(t[x].son[0],t[x].tag[1],1),tager(t[x].son[1],t[x].tag[1],1),tager(t[x].son[2],t[x].tag[1],1),tager(t[x].son[2],t[x].tag[1],0),t[x].tag[1]=Tag();
  }else{
    if(t[x].reved)rever(t[x].son[0]),rever(t[x].son[1]),t[x].reved=0;
    if(!t[x].tag[0].empty())tager(t[x].son[0],t[x].tag[0],0),tager(t[x].son[1],t[x].tag[0],0),t[x].tag[0]=Tag();
    if(!t[x].tag[1].empty())tager(t[x].son[0],t[x].tag[1],1),tager(t[x].son[1],t[x].tag[1],1),tager(t[x].son[2],t[x].tag[1],1),t[x].tag[1]=Tag();
  }
}
//链信息修改只有 compree tree 才需要下传。
//更多的标记下传参见 Sone1
il vd update(int x,bl o){if(!isroot(x))update(t[x].fa,o);pushdown(x,o);}

rotate

就是 splay 的旋转操作，判断自己是左儿子还是右儿子，再重新接到父亲上。记得特判父亲是否存在。

LCT 省流：原先的判断爷节点是否是当前 splay 的根改为是否存在。

il vd rotate(int x,bl o){
  int y=t[x].fa,z=t[y].fa;bl w=get(x);
  if(z)t[z].son[get(y)]=x;//注意判断条件的变换 
  t[x].fa=z,connect(y,t[x].son[w^1],w),connect(x,y,w^1);
  pushup(y,o),pushup(x,o);
}

splay

将节点旋转到当前 rake 树或 compress 树的根。

记得要双旋，若是同方向需要先旋转父亲。

为了方便后面删除需要实现旋转到指定节点下的操作。

LCT 省流：需要实现旋转到指定节点下的操作。

il vd splay(int x,bl o,int y=0){//为了方便删除，需要新添加旋转到 y 子树的功能。
  for(update(x,o);!isroot(x)&&t[x].fa^y;rotate(x,o))
  if(!isroot(t[x].fa)&&t[t[x].fa].fa^y)rotate(get(t[x].fa)^get(x)?x:t[x].fa,o);
}

strike

这是我自己取的名，意为罢工，很形象吧。

删除罢工一个 rake 节点。

如果两个儿子都有就实现经典的删除操作即可。否则直接接上。

具体可以看代码。

il vd strike(int x){//rake 节点，此时 x 无中儿子，罢工 x。 
  if(t[x].son[0]){
    int y=t[t[x].son[0]].rp;splay(y,1,x),connect(y,t[x].son[1],1);
    connect(t[x].fa,y,2),pushup(y,1);
    //经典的删除操作，把最右边的点旋上来，再把右儿子接进去。 
  }else connect(t[x].fa,t[x].son[1],2);
  //没有左儿子就不需要合并了。 
  pushup(t[x].fa,0),st[++top]=x;
}

splice

核心操作，意为将一个 rake 节点的中儿子跨越她的 rake 树，即把中儿子接到自己父亲的 compress 树上。

体现在原树上，就是改变簇路径。

实现需要两步：

local splay：将中儿子的父节点和爷节点都旋转到其所在二叉树的根。

splice：跨越 rake 树。如果爷节点有右儿子直接交换就可以了，否则就会出现无意义的 rake 节点，需要删除罢工。

il vd splice(int x){//rake 结点，将中儿子跨越 rake tree 
  //local splay：将自己的父节点和爷节点都转到指定树的根。 
  splay(x,1);int y=t[x].fa;splay(y,0),pushdown(x,1);
  //splice：将 x 的中儿子跨越它的 rake tree 
  if(t[y].son[1])swap(t[t[x].son[2]].fa,t[t[y].son[1]].fa),swap(t[x].son[2],t[y].son[1]),pushup(x,1),pushup(y,0);
  //有右儿子就直接交换，对应更改簇路径。
  else connect(y,t[x].son[2],1),strike(x),pushup(y,0);
  //没有就删除 x 这个 wyy 结点 
}

access

打通根到指定点的实链作为簇路径。

首先将节点变成界点，然后不断跨越 rake 树即可。

LCT 省流：只需增加将节点变为界点操作即可。

il vd access(int x){//compress 结点，打通其到根的链作为根簇路径
  splay(x,0);
  if(t[x].son[1]){//x 不是簇的端点，将右儿子掰下来，变成 rake tree。 
    int y=neww();connect(y,t[x].son[2],0),connect(y,t[x].son[1],2);
    t[x].son[1]=0,connect(x,y,2),pushup(y,1),pushup(x,0);
  }
  for(;t[x].fa;splay(x,0))splice(t[x].fa);
  //不断跨越 rake tree 即可。
  //一个性质是 access 完后 x 已经是 compress tree 的根了。 
}

零散操作

都不难理解，不多赘述。

mkroot：定根。

split：打通路径作为簇。

fdroot：找根。

il vd mkroot(int x){access(x),rever(x);}
il vd split(int x,int y){mkroot(x),access(y);}
il int fdroot(int x){return access(x),t[x].lp;}

子树操作

这里单独记一下。打通指定节点到根的路径以后，她的右儿子应该是空的，她的中儿子和她本身就是她的子树。

本题代码

本题的操作都比较基础，自己实现不难。这里给出一份封装的 SATT 代码。

namespace SATT{
  //0:compress 1:rake
  int st[N*3],top,Node;
  struct node{
    int fa,son[3],lp,rp,v,sum[2];bl reved;
    node(){fa=son[0]=son[1]=son[2]=lp=rp=v=sum[0]=sum[1]=reved=0;}
  }t[N*3];
  #define isroot(x) (t[t[x].fa].son[0]^x&&t[t[x].fa].son[1]^x)
  #define get(x) (t[t[x].fa].son[0]==x?0:t[t[x].fa].son[1]==x?1:2)
  #define connect(x,y,w) (t[x].son[w]=y,y&&(t[y].fa=x))
  il int neww(){int x=top?st[top--]:++Node;t[x]=node();return x;}
  il vd pushup(int x,bl o){
    t[x].lp=t[x].son[0]?t[t[x].son[0]].lp:x,t[x].rp=t[x].son[1]?t[t[x].son[1]].rp:x;
    if(o){//rake
      t[x].sum[1]=t[t[x].son[0]].sum[1]^t[t[x].son[2]].sum[1]^t[t[x].son[1]].sum[1];
      //rake tree 的 pushup 是所有点的 compress 中儿子的合并。 
    }else{//compress
      t[x].sum[0]=t[t[x].son[0]].sum[0]^t[x].v^t[t[x].son[1]].sum[0];
      //compress tree 信息，直白的说就是簇路径信息。 
      t[x].sum[1]=t[t[x].son[0]].sum[1]^(t[t[x].son[2]].sum[1]^t[x].v)^t[t[x].son[1]].sum[1];
      //簇信息，中间的一部分表示 t[t[x].son[2]].sum[1] 作用在 t[x].v 上的更新。 
    }
  }
  il vd rever(int x){if(x)swap(t[x].son[0],t[x].son[1]),swap(t[x].lp,t[x].rp),t[x].reved^=1;}
  il vd pushdown(int x,bl o){if(!o&&t[x].reved)rever(t[x].son[0]),rever(t[x].son[1]),t[x].reved=0;}
  //链信息修改只有 compree tree 才需要下传。
  //更多的标记下传参见 Sone1 
  il vd update(int x,bl o){if(!isroot(x))update(t[x].fa,o);pushdown(x,o);}
  il vd rotate(int x,bl o){
    int y=t[x].fa,z=t[y].fa;bl w=get(x);
    if(z)t[z].son[get(y)]=x;//注意判断条件的变换 
    t[x].fa=z,connect(y,t[x].son[w^1],w),connect(x,y,w^1);
    pushup(y,o),pushup(x,o);
  } 
  il vd splay(int x,bl o,int y=0){//为了方便删除，需要新添加旋转到 y 子树的功能。
    for(update(x,o);!isroot(x)&&t[x].fa^y;rotate(x,o))
    if(!isroot(t[x].fa)&&t[t[x].fa].fa^y)rotate(get(t[x].fa)^get(x)?x:t[x].fa,o);
  } 
  il vd strike(int x){//rake 结点，此时 x 无中儿子，罢工 x。 
    if(t[x].son[0]){
      int y=t[t[x].son[0]].rp;splay(y,1,x),connect(y,t[x].son[1],1);
      connect(t[x].fa,y,2),pushup(y,1);
      //经典的删除操作，把最右边的点旋上来，再把右儿子接进去。 
    }else connect(t[x].fa,t[x].son[1],2);
    //没有左儿子就不需要合并了。 
    pushup(t[x].fa,0),st[++top]=x;
  }
  il vd splice(int x){//rake 结点，将中儿子跨越 rake tree 
    //local splay：将自己的父节点和爷节点都转到指定树的根。 
    splay(x,1);int y=t[x].fa;splay(y,0),pushdown(x,1);
    //splice：将 x 的中儿子跨越它的 rake tree 
    if(t[y].son[1])swap(t[t[x].son[2]].fa,t[t[y].son[1]].fa),swap(t[x].son[2],t[y].son[1]),pushup(x,1),pushup(y,0);
    //有右儿子就直接交换，对应更改簇路径。
    else connect(y,t[x].son[2],1),strike(x),pushup(y,0);
    //没有就删除 x 这个 wyy 结点 
  }
  il vd access(int x){//compress 结点，打通其到根的链作为根簇路径
    splay(x,0);
    if(t[x].son[1]){//x 不是簇的端点，将右儿子掰下来，变成 rake tree。 
      int y=neww();connect(y,t[x].son[2],0),connect(y,t[x].son[1],2);
      t[x].son[1]=0,connect(x,y,2),pushup(y,1),pushup(x,0);
    }
    for(;t[x].fa;splay(x,0))splice(t[x].fa);
    //不断跨越 rake tree 即可。
    //一个性质是 access 完后 x 已经是 compress tree 的根了。 
  }
  il vd mkroot(int x){access(x),rever(x);}
  il vd split(int x,int y){mkroot(x),access(y);}
  il int fdroot(int x){return access(x),t[x].lp;}
  il vd link(int x,int y){if(fdroot(x)==fdroot(y))return;access(x),mkroot(y),connect(x,y,1),pushup(y,0),pushup(x,0);}
  il vd cut(int x,int y){split(x,y);if(t[y].son[0]^x||t[x].son[1])return;t[x].fa=t[y].son[0]=0,pushup(y,0);}
}using namespace SATT;

总结

只要记住了几个关键函数，SATT 不难实现。

一定时刻注意分讨 rake 节点和 compress 节点。

题外话

其实总体来看，SATT 并不算一个特别难理解的结构，代码实现难度和 LCT 差不多。

但人心中的成见是一座大山，仅因为她是 TopTree 便长期被人诟病。

故普及 SATT 是有必要的，所以有了这篇题解。

如果有兴趣的话可以继续了解静态 TopTree 理论，也是简单又强势的数据结构。推荐同学的文章，主要是有完整代码和资料目录。

板子题一定不能出问题，如果有问题请指出，感激不尽！