学习笔记 - LCT

数据结构也开始复习（学新的，虽然在纪中那边自学过）了

代码量非常友ke好guan

---

Part1. 动态树问题

要求动态维护一个森林，支持删边加边（保证加边后仍是森林，即不会出现环），以及修改点权等操作。

对于森林的形态，支持以下：

• Link(u,v)：在 u,v 两点间连边 (u,v)；
• Cut(u,v)：断掉边 (u,v)；
• FindRoot(u)：找到 u 现在所在的树的根；

对于点权值，支持：

• 修改/询问一条路径上的值；
• 修改/询问一棵子树中的值；

现在已经出现的实现动态树问题的算法，公认单次操作的时间复杂度为 $O(\log_2n)$ 。其中 Link-Cut Tree(LCT) 是一种比较简单的解决动态树问题的数据结构。

实际上，现有的解决动态树问题的方法都是 “把原树等价对应到一棵深度平均($\log_2n$)的辅助树”

---

Part2. Link-Cut Tree(LCT)

为了达到 $O(\log_2n)$ 的单次复杂度，LCT 以 Splay 为内部数据结构。其核心操作是 Access(u)。

Part2/1. 实链剖分

类似于树链剖分中的“重链剖分”，实链剖分也是把树剖分成若干条 各点深度不同的链。链上的边是实边，不在链上的边是虚边。

也可以这样理解：每个节点有最多一个 优先儿子（类似于重链剖分的重儿子），该点到它的优先儿子的边为实边，到其他儿子的边为虚边。

比如这样就是实链剖分：

Part2/2. Splay 的节点结构体

Hint. 下面的一些函数是定义在一个结构体中的：

struct LNODE *NIL;
struct LNODE{
	int Vsiz,Brev;
	LNODE *fa,*ch[2];
    //判断 u 是父亲的左儿子还是右儿子
	inline int Direc(){return fa->ch[1]==this;}
    //判断 u 是否是当前 Splay 的根
	inline bool IfRoot(){return fa==NIL || (fa->ch[0]!=this && fa->ch[1]!=this);}
	inline void SetChild(LNODE *Pch,int dir){ //修改 u 的儿子为 Pch，dir=0为左儿子，dir=1为右儿子
		ch[dir]=Pch;
		if(Pch!=NIL) Pch->fa=this;
	}
	inline void PushUp(){
		if(this==NIL) return;
		Vsiz=ch[0]->Vsiz+ch[1]->Vsiz+1;
	}
    //下传反转标记
	inline void PushDown(){
		if(!Brev) return;
		if(ch[0]!=NIL) ch[0]->Brev^=1;
		if(ch[1]!=NIL) ch[1]->Brev^=1;
		swap(ch[0],ch[1]);
		Brev=0;
	}
};

Part2/3. Splay

LCT 的辅助树（还记得什么是辅助树吗）是由多棵 Splay 维护的，其中每棵 Splay 维护的是树上的一条实链，每个点的权值为点的深度。所以可以得到，在同一棵 Splay 中，“左儿子的深度<根的深度<右儿子的深度”（而且每条实链上的点深度都不同，所以 Splay 里的每个点深度都不同）。

• 如果边 (u,v) 是实边，在辅助树上体现为 u,v 在同一棵 Splay 中；
• 如果边 (u,v) 是虚边，在辅助树上体现为 “u所在的实链的最高点top[u]的父亲指针指向v，但是v的孩子指针没有指向top[u]”，即 认父不认子。

Part2/4. Rotate(u) & Splay(u)

虽然 Splay 是 LCT 的内部结构，但是实际实现时对 Splay 有所修改。由于 LCT 并不需要知道每棵 Splay 的根具体是谁，只需要知道某个点是不是 Splay 的根就行了。

判断一个点 u 是否是该 Splay 的根其实比较简单：① u 的父亲是 null （非常显然）；② u 到 u的父亲 的边是虚边，只要判断在 Splay 中 u的父亲 是否存在一个儿子为 u。

inline bool IfRoot(){ //this 指向 节点u
	return fa==NIL || (fa->ch[0]!=this && fa->ch[1]!=this);
}

首先 Splay(u) 操作只会在 u 所在的 Splay 中操作，也就是只会在 u 所在的实链上操作。所以对应的，Rotate(u),Splay(u) 有几处修改：

void Rotate(LNODE *x){
	LNODE *y=x->fa;
	y->PushDown();x->PushDown();
	int dir=x->Direc();
	if(y->IfRoot()) x->fa=y->fa; //如果 y 是当前 Splay 的根节点，只能连虚边
	else y->fa->SetChild(x,y->Direc());
	y->SetChild(x->ch[!dir],dir);
	x->SetChild(y,!dir);
	y->PushUp();
}
void Splay(LNODE *x){
    stack<LNODE*> stk;
    while(!x->IfRoot()) stk.push(x);
	x->PushDown();
    while(!stk.empty()) stk.top()->PushDown(),stk.pop();
    //Splay 的 PushDown 必须要从上到下 PushDown
	while(!x->IfRoot()){ //这里判断当前 Splay 的根
		LNODE *y=x->fa;
		if(y->IfRoot()) Rotate(x); //同上
		else{
			if(x->Direc()==y->Direc()) Rotate(y);
			else Rotate(x);
			Rotate(x);
		}
	}
	x->PushUp();
}

Part2/5. Access(u)操作

用函数 Access(u) 来实现将 u 到 原树的根 这条链全部变成实链，并且把 u 的儿子全部变成轻儿子。比如这样

Hint. 注意是原树

把 u 的儿子都设为轻儿子其实就是在 Splay 上把深度大于 u 的点与 u 的边改为虚边。所以我们先 Splay(u)，然后 u 的右子树就是 Splay 里深度比 u 大的点，所以再把 u 的右儿子设为虚边即可（也就是 u->ch[1]=NIL）。

接下来把 u的父亲 与它的优先儿子（如果有的话）之间的实边断开，重新设 u 为 u的父亲 的优先儿子；也就是把 u 的父节点（父节点与 u 就不在一条链上了）的右儿子改为 u。把 u 移到父节点，然后继续……

代码是这样实现的：

void *Access(LNODE *x){
	LNODE *y=NIL; //用来保存上一个 x
	while(x!=NIL){
		Splay(x); //先转到 Splay 的根
		x->SetChild(y,1); //断开原来与优先儿子的实边，并将右儿子的边设为实边
		x->PushUp();
		y=x;x=x->fa; //上移一层处理
	}
}

Part2/6. MakeRoot(u) & Link(u,v) & Cut(u,v)

即把 u 改为它所在树的根（不改变形态），在 u,v 之间连上边（需要保证 u,v 不在同一棵树中）和断开 (u,v) 之间的边（需要保证 u,v 之间原来有边）。

Hint. 这里换根、连边、断边是在原树上

我们先把 u 到它的根的路径打通 Access(u)，然后就形成了一条 u 到根的链，可以知道 u 是该链中深度最大的点。然后再 Splay(u)，因为该链中的其他点的深度都小于 u，所以 u 只有左儿子。这个时候，我们只要把这条链整个反转就可以把 u 改为链中深度最小的点，也就是整棵树的根了。

void MakeRoot(LNODE *x){
	Access(x);Splay(x);
	x->Brev=true; //反转标记（懒标记）
}

有了 MakeRoot()，Link(u,v) 就简单多了。只要把 x 改为当前树的根，然后把 x 接到 y 的下面、作为 y 的子树就可以了。

void Link(LNODE *x,LNODE *y){
	MakeRoot(x);
	x->fa=y;
}

另外 Cut(u,v) 也比较好理解：先把 u 改为当前树的根，就可以通过 Access(v) 来打通 u 到 v 的路径，然后 Splay(v) 就可以使 u,v 相邻，而且 u 是 v 的左儿子。此时只要断开 u,v 之间的边。

void Cut(LNODE *x,LNODE *y){
	MakeRoot(x);
	Access(y);Splay(y);
	y->ch[0]=NIL;y->PushUp();
	x->fa=NIL;
}

---

Part3. LCT 的其他操作

Part3/1. 连通任意两点的路径

只要是无根树，我们就可以随意 MakeRoot()；所以只要把路径一端 u 改为树的根，就可以通过 Access(v) 打通 u 到 v 的路径了。

LNODE *Road(LNODE *x,LNODE *y){
	MakeRoot(x);
	Access(y);Splay(y); //Splay 过后 y 就存储了整个 Splay 也就是从u到v的路径的信息了
	return y;
}

Part3/2. 求 LCA

需要理解一下：先 Access(u)，再 Access(v)，最后 Splay(u)，然后就会有两种情况。

1. 

   当 LCA 不为 u（也就是 u 不是 v 的祖先）时， fa[u] 就是 LCA。

2. 

   此时再 Splay(u)，fa[u] 就为空，此时可以判断出 u 本身就是 LCA。

LNODE *LCA(LNODE *x,LNODE *y){
	Access(x);
	Access(y);
	Splay(x);
	if(x->fa==NIL) return x;
	else return x->fa;
}

---

Part4. LCT版子

struct LNODE *NIL; //可以这样在定义结构体之前声明结构体变量
struct LNODE{
    int Vsiz,Vsum,Vval; //这里就维护链上的权值和
    //Vsiz：Splay中该子树的大小；Vsum：Splay中该子树的元素和；Vval：该点的权值
    bool Brev; //反转标记
    LNODE *ch[2],*fa;
    void PushUp(){
        if(this==NIL) return;
        ch[0]->PushDown();ch[1]->PushDown(); //我的写法中只有PushDown过后该节点才会是真实值
        Vsiz=ch[0]->Vsiz+ch[1]->Vsiz+1;
        Vsum=ch[0]->Vsum+ch[1]->Vsum+Vval;
    }
    void PushDown(){
        if(Brev){
            Brev=false;
            swap(ch[0],ch[1]);
            if(ch[0]!=NIL) ch[0]->Brev^=1;
            if(ch[1]!=NIL) ch[1]->Brev^=1;
        }
    }
    bool IfRoot(){return fa==NIL || (fa->ch[0]!=this && fa->ch[1]!=this);}
    bool Direc(){return fa->ch[1]==this;}
    void SetChild(LNODE *Pch,int dir){
        ch[dir]=Pch;
        if(Pch!=NIL) Pch->fa=this;
    }
};
struct LCT{
    LNODE Lpol[N+3]; //内存池
    void Init(){ //初始化
        NIL=Lpol;
        NIL->ch[0]=NIL->ch[1]=NIL->fa=NIL;
        NIL->Vsiz=NIL->Vsum=NIL->Vval=0;
    }
    LNODE *Ind(int id){return Lpol+id;} //取得 Lpol[id] 的指针
    void NewNode(int id,int Vv){ //将编号为 id 的点初始化点权为 Vv
        LNODE *p=Ind(id);
        p->Vsum=p->Vval=Vv;
        p->Vsiz=1;
        p->ch[0]=p->ch[1]=p->fa=NIL;
    }
    void Rotate(LNODE *x){
        LNODE *y=x->fa;
        int dir=x->Direc();
        if(y->IfRoot()) x->fa=y->fa;
        else y->fa->SetChild(x,y->Direc());
        y->SetChild(x->ch[!dir],dir);
        x->SetChild(y,!dir);
        y->PushUp();
    }
    void Splay(LNODE *x){
        stack<LNODE*> stk; //一定要从上到下 PushDown
        for(LNODE *y=x;;y=y->fa){
            stk.push(y);
            if(y->IfRoot()) break;
        }
        while(!stk.empty()){
            stk.top()->PushDown();
            stk.pop();
        }
        while(!x->IfRoot()){
            LNODE *y=x->fa;
            if(y->IfRoot()) Rotate(x);
            else{
                if(x->Direc()==y->Direc()) Rotate(y);
                else Rotate(x);
                Rotate(x);
            }
        }
        x->PushUp();
    }
    void Access(LNODE *x){
        LNODE *y=NIL;
        while(x!=NIL){
            Splay(x);
            x->SetChild(y,1);
            x->PushUp();
            y=x;x=x->fa;
        }
    }
    void MakeRoot(LNODE *x){
        Access(x);Splay(x);
        x->Brev^=1;
    }
    LNODE *FindRoot(LNODE *x){
        Access(x);Splay(x);
        while(x->ch[0]!=NIL) x=x->ch[0];
        Splay(x);
        return x;
    }
    void Link(LNODE *x,LNODE *y){
        MakeRoot(x);
        x->fa=y;
    }
    void Cut(LNODE *x,LNODE *y){
        MakeRoot(x);
        Access(y);Splay(y);
        y->ch[0]=NIL;y->PushUp();
        x->fa=NIL;
    }
    LNODE *Road(LNODE *x,LNODE *y){
        MakeRoot(x);
        Access(y);Splay(y);
        return y;
    }
    LNODE *LCA(LNODE *x,LNODE *y){ //注意 MakeRoot 过后 LCA 可能会变
        Access(x);
        Access(y);
        Splay(x);
        if(x->fa==NIL) return x;
        else return y;
    }
}

---

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问~