【模板】动态树LCT

用Splay解决序列区间问题
用树剖解决序列问题上树
用LCT解决形状变化的树剖 ——VCode

前置技能:树链剖分,Splay

树剖要求到知道怎么回事的程度。

Splay要求到能支持基本操作的程度。

P1 给一个序列,问区间xor和

A1 前缀和

P2 给一个序列,带修改,问区间xor和。

A2 树状数组/线段树

P3 给一棵树,带修改,问链xor和。

A3 树剖

P4 给一棵树,带修改,可以改变树上连边的情况,问链xor和。

这时候就需要我们的LCT出场了!

树链剖分与LCT

我们大家都会熟练剖分(啪)。

树链剖分常见有几种剖法。一种按长度剖,一种按重量剖。

当然为了解决我们的link和cut的问题,我们还需要一种剖分方法,就是瞎剖。

当然不是随机剖分,而是按照最近访问过的儿子和不是最近访问过的儿子来剖分。

也就是说,当我们访问了一个节点,我们就让根到这个节点之间的路径变成重链。

当然我们知道一个节点是不会有两个重儿子的,所以如果有冲突的地方就把原来的重边变回轻边,它已经不适合现在这个版本了。

特殊地,我们所想访问的那个节点的重儿子摸掉,使其变成轻儿子。因为这样一来,根到这个节点的的路径就是一条完整的重链了。

好了,现在你已经学会了LCT。

那么问题来了,这么个恶心的东西,代码要怎么写?!

Splay与树链剖分与LCT

树链剖分是用数据结构维护链的。但是这个链如此善变,肯定不能再用线段树了。于是我们需要考虑同样善变的Splay。

Splay可以解决一切线段树可以解决的问题,除了线段树优化建图。 ——VCode

这句话有bug吧。Splay怎么做SegmentTreeBeats。 ——Xenoacid

对于每个LCT上的节点,我们对应Splay上的一个节点。

对于每个LCT上的重链,我们开一棵以深度为关键字排序的Splay来维护。

当重链断开时,我们让Splay断开。

当有重链连接时,我们将Splay连接。

当询问一条链上的信息时,我们直接在Splay上操作。

现在我们知道用Splay可以维护所有重边了,但是轻边怎么办?

我们回忆一下Splay的根节点的父亲,一般都是空。但是我们可以利用一下这个信息,让轻边下面的点所对应的Splay的根节点的父亲设置为轻边上面的点。

于是我们就会看到一个神奇的现象,一个点$A$是另一个点$B$的父亲(Splay上),但点$B$却既不是$A$的左儿子也不是$A$的右儿子。这时候我们就知道$A$和$B$之间有一条轻边。

也许你看到这里还是很迷,不知道怎么写。没关系,让我们继续看下去,你会发现,根本不需要维护原树,你所需要维护的只有一堆Splay而已。

实现

首先,假设我们已经会写了一个$access(x)$操作,表示访问一下节点$x$,使根到$x$的路径变为重链。

当然还有你应该早就会了的$splay(x)$操作,表示把$x$转为这棵Splay的根。

Let’s go!

makeRoot(x)

反正我们都是动态树了,我们干脆就让它动一动,让它可以换根。

我们可以先访问一下新的根节点并$splay$一下,然后打上子树反转标记。

这样一来,原来在左子树的东西就都跑到右子树了,相当于在原树上深度大小变了,也就是换了根。

void makeRoot(int now) {
  access(now);
  splay(now);
  reverse(now);//Splay子树翻转
}

split(a, b)

让$a$与$b$之间的路径成为一条重链。

void split(int a, int b) {
  makeRoot(a);
  access(b);
  splay(b);//礼貌性splay一下,同时可以简化cut代码。
}

把$a$和$b$之间连一条新边。

先考虑一定合法,也就是$a$和$b$不在同一棵LCT中的情况。

void link(int a, int b) {
  makeRoot(a);
  node[b].fa = a;
  //access(b);可以礼貌性访问一下,但没必要。
}

完美。

但是如果在同一棵LCT怎么办?

void link(int a, int b) {
  makeRoot(a);
  if(findRoot(b) == a) return;//加这一句就好了。
  node[b].fa = a;
  //access(b)
}

$findRoot(x)$就是找到$x$的LCT的根。怎么写一会再说。

cut(a, b)

断开$a$和$b$之间的边。

先考虑一定合法,也就是$a$和$b$之间有边的情况。

void link(int a, int b) {
  split(a, b);
  node[b].son[0] = NIL;
  node[a].fa = NIL;
  update(a);//更新Splay信息
}

然后考虑什么情况下不合法:

  1. a和b不在一棵LCT里
  2. a和b在一棵LCT里,但a和b之间还有其他节点

优先考虑第二种情况。此时在Splay中的表现有两种情况:

  1. b为根时,a不是b的左儿子
  2. b为根时,a是b的左儿子,但a有右儿子

再考虑a和b不在同一棵LCT中的情况。显然满足第二种情况中说的“b为根时,a不是b的左儿子”。

于是可以在代码里加一句就可以了:

void cut(int a, int b) {
  split(a, b);
  if(node[b].son[0] != a || node[a].son[1] != NIL) return;
  node[b].son[0] = NIL;
  node[a].fa = NIL;
  update(b);
}

还有我们刚才跳过的两个操作,$access(x)$和$findRoot(x)$

access(x)

你会发现我们没有记录LCT的根,所以我们需要从下往上走。

沿着重链向上跳,遇到轻链就修改成重链,直到Splay根为空就可以了。

void access(int now) {
  int last = NIL;//NIL = -1
  while(~now) {
    splay(now);//now变为Splay根
    node[now].son[1] = last;//更改轻重边状态
    update(now);
    last = now;
    now = node[now].fa;
  }
}

findRoot(x)

看完$access(x)$你真的就一点想法都没有吗?

int findRoot(int now) {
  access(now);
  splay(now);
  while(now != NIL) {
    pushdown(now);//Splay pushdown
    if(node[now].son[0] == NIL) break;
    now = node[now].son[0];
  }
  return now;
}

现在我们已经可以写出LCT了,需要区间异或就在Splay维护异或,需要深度就维护深度之类的即可,矛盾具有特殊性(具体问题具体分析)。

复杂度分析

不会,Tarjan告诉我是$nlogn$

【模板】Link Cut Tree (动态树)
[HNOI2010]弹飞绵羊

LCT乍一看很难,但熟练之后会发现其实挺好写的。

代码