LCT 学习笔记（持续更新中）

Link-Cut-Tree 学习日记

前置知识:\(Splay\)

对于一般维护链上问题的最优选择一般是选择树剖，但是如需要动态加减边时，树剖就显得手无缚鸡之力，这时就需要 \(Link-Cut-Tree\)

对于树链剖分来说，我们以轻重儿子来划分链，源于这样的性质就不方便修改，所以在 \(LCT\) 中，我们就考虑“实链剖分”，我们考虑自己钦定一些边中的一条为实边，反之则为轻边。相应的，我们令实边连接的儿子叫实儿子，同样虚边连接的儿子叫虚儿子。这样就有个很好的性质：我们可以灵活的改变，在这样的情况下，我们选择用 \(Splay\) 树来维护这些实链。（其实也可以用 \(FHQ\) 维护，但是会多一个 \(log\) , 而且蒟蒻我不会）

1.辅助树

概念：一些 \(Splay\) 构成了一个辅助树，每棵辅助树维护的是一棵树，一些辅助树构成了 \(LCT\)，其维护的是整个森林。（摘自oi-wiki）

首先，一颗辅助树由多颗 \(Splay\) 构成，每一个 \(Splay\) 维护原树的一条路径（所以\(Splay\) 中节点与原树一一对应），在 \(Splay\) 树中，我们维护 \(Splay\) 的中序遍历点序列的深度单调增。

另外，辅助树中各个 \(Splay\) 并非是独立的，每颗 \(Splay\) 的根节点的父亲都指向原树这条实链的父亲，这叫认爹不认儿。这样无论我们怎么操作，那个原树是不会变的，所以我们可以不维护原树，只维护辅助树即可。

原树:

他的辅助树：

有了以上这些性质我们可以发现 :

1.虚实链的变换可以轻松在辅助树上完成

2.辅助树可以在满足辅助树和 \(Splay\) 性质下任意改变根节点的

OK 前置大概讲完了，来看代码

代码

这里以 P3690 【模板】动态树（LCT） 为例

定义：

\(c[N][2]\) 左右儿子

\(f[N]\) 父亲指向

\(s[N]\) 路径权值

\(v[N]\) 这个点的权值

\(r[N]\) 翻转标记

1 ： Not_root()

#define Not_root(x)c[f[x]][0] == x || c[f[x]][1] == x;

判断一个节点是不是根：当自己爹的儿子不是自己的时候，说明他们不在同一颗 \(Splay\) 上，因为（认爹不认儿）， 所以这个点就是根（他指向他爹了），反之则不是根

有很多大佬都写得 Is_root 但是我觉得还是 Not_root 更方便

2 ：pushup()

#define pushup(x) s[x]=s[ls]^s[rs]^v[x]

很显然不再赘述

3 ： pushr()

#define pushr(x) swap(ls,rs),r[x]^=1

翻转左右儿子并打标记，至于为什么这样后面会说

4：pushdown()

void pushdown(int x){if(r[x]){if(ls)pushr(ls);//不判也可if(rs)pushr(rs);r[x] = 0;}
}

下放翻转标记

5：\(Splay\) 部分

int dir(int x){return c[f[x]][1] == x;}
void rotate(int x){int y = f[x] , z = f[y] , k = dir(x) , w = c[x][!k];if(Not_root(y))c[z][dir(y)] = x; //与 Splay 的不同之处c[x][!k] = y , c[y][k] = w; if(w)f[w] = y;f[y] = x, f[x] = z; pushup(y);
}
void splay(int x){int y = x , top = 0;sta[++top] = x;// 与Splay不同 , 我们先从上到下把标记下放while(Not_root(y))sta[++top] = y = f[y]; while(top)pushdown(sta[top--]);while(Not_root(x)){y = f[x];if(Not_root(y))rotate(dir(x) == dir(y) ? y : x);rotate(x);}pushup(x);
}

\(\Huge 最重要的部分！\)

6：access()

\(access\) 是 LCT 的核心操作，其作用就是从他到\(Splay\)根拉一条实链

有这样一棵树，实线为实边，虚线为虚边。

他的辅助树是这样的

现在我们要 access(N) ，把 \(A\) 到 \(N\) 路径上的边都变为实边，拉成一棵 \(Splay\)。

实现的方法是从下到上逐步更新 \(Splay\)

首先我们要把 \(N\) 旋至当前 \(Splay\) 的根 , 为了保证辅助树的性质，原来 \(N\) 到 \(O\) 的实边要更改为虚边。由于认父不认子的性质，我们可以单方面的把 \(N\) 的儿子改为 \(nullptr\)。

就变成这样了

我们把 \(N\) 指向的爹 \(I\) 也旋转到 \(I\) 的 \(Splay\) 树根 ，然后把 \(I\) 的儿子指向 \(N\)

之后同理,最后变成了这样

总结一下，就是：

1. 把当前节点转到根。

2. 把儿子换成之前的节点。

3. 更新当前点的信息。

4. 把当前点换成当前点的父亲，继续操作。

void access(int x){for(int y = 0;x;x = f[y = x]){splay(x),rs = y,pushup(x);}
}

7：make_root

void make_root(int x){access(x);splay(x);pushr(x);
}

先把x拉一到根的链，然后让x变成根，最后打上翻转标记

为什么打翻转标记呢？

\(makeroot\) 定义为换根，即让指定点成为原树的根。

这时候就利用到 \(access(x)\) 和 \(Splay\) 的翻转操作。

\(access(x)\) 后 \(x\) 一定是Splay中序遍历最后的点，此时 \(x\)在\(Splay\)中将没有右子树。于是翻转整个\(Splay\)，使得所有点的深度都倒过来了，\(x\)没了左子树，成了深度最小的点，达到了我们的目的,相当于互换左右儿子。

8：findroot

int find_root(int x){access(x);splay(x);while(ls)pushdown(x),x = ls;splay(x);return x;
}

我们把\(x\)转到根，然后一直找左儿子，因为左儿子的深度比自己小，最深的就是原树的根

9：split

void split(int x,int y){make_root(x);access(y);splay(y);
}

\(split\) 是指把从\(x\)到\(y\)路径拉成一个\(Splay\)

10：link

void link(int x,int y){make_root(x);if(find_root(y) != x)f[x] = y;  
}

\(link\) 连接\(x\)到\(y\)

cut

void cut(int x,int y){make_root(x);if(find_root(y) == x and f[y] == x and !c[y][0]){f[y] = c[x][1] = 0;pushup(x);}
}

将从\(x\) 到 \(y\) 的边断开。

\(x\) 变成根后，\(y\) 的父亲一定指向\(x\) ，深度相差一定是1

所以当\(access(y)\) - \(splay(y)\)以后，\(x\) 一定是 \(y\) 的左儿子，断开连接就可以

例题

维护链信息

1. P3690 【模板】动态树（LCT）

2. P1501 [国家集训队] Tree II

3. P3203 [HNOI2010] 弹飞绵羊

4. P2486 [SDOI2011] 染色

5. P4332 [SHOI2014] 三叉神经树

除了5都比较板子，弹飞绵羊有分块做法，三叉神经树需要认真思考性质

动态维护连通性&&双联通分量

1. P2147 [SDOI2008] 洞穴勘测 维护连通性

2. P3950 部落冲突 双倍经验

3. P2542 [AHOI2005] 航线规划 维护双联通分量，每次暴力缩点，因为只有n个节点，所以复杂度是对的，直接暴力修改并查集上的爹

附上代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long 
const int M = 1e6 + 20;
#define ls c[x][0]
#define rs c[x][1]
int n , m , s[M] , cnt , h[M] , mn[M] , c[M][2] , f[M] , r[M] , sta[M] , top;
int dir(int x){return c[f[x]][1] == x;
}
int geth(int x){if(x != h[x])return h[x] = geth(h[x]);return x;
}
int Not_root(int x){return c[f[x]][1] == x || c[f[x]][0] == x;
}
void pushr(int x){swap(ls , rs);r[x] ^= 1;
}
void pushdown(int x){if(r[x]){if(ls)pushr(ls);if(rs)pushr(rs);r[x] = 0;}
}
void pushup(int x){s[x] = s[ls] + s[rs] + 1;
}
void rotate(int x){int y = f[x] , z = f[y] , k = dir(x) , w = c[x][!k];if(Not_root(y))c[z][dir(y)] = x;c[x][!k] = y;c[y][k] = w;if(w)f[w] = y;f[x] = z , f[y] = x;pushup(y);
}
void splay(int x){int y = x , top = 0;sta[++top] = y;while(Not_root(y))sta[++top] = y = f[y];while(top)pushdown(sta[top--]);while(Not_root(x)){int y = f[x];if(Not_root(y))rotate(dir(x) == dir(y)? y : x);rotate(x);}pushup(x);
}
void access(int x){for(int y = 0;x;y = x , x = f[y] = geth(f[x])){splay(x) , c[x][1] = y , pushup(x);}
}
void make_root(int x){access(x);splay(x);pushr(x);
}
int find_root(int x){access(x);splay(x);while(ls)pushdown(x),x = ls;splay(x);return x;
}
void split(int x,int y){make_root(y);access(x);splay(x);
}
struct edge{int u , v;	bool operator < (const edge &a)const{return u < a.u || (u == a.u && v < a.v);}
}e[M];
void link(int x,int y){make_root(x);if(find_root(y) != x)f[x] = y;
}
void cut(int x,int y){make_root(x);if(find_root(y) == x && f[y] == x && !c[y][0]){f[y] = c[x][1] = 0;pushup(x);}
}
int vis[M] , op[M] , u[M] , v[M];void del(int x , int y){if(x)h[x] = y , del(ls , y) , del(rs , y);
}
void merge(int x,int y){if(x == y)return;make_root(x);if(find_root(y) != x){f[x] = y;return;}del(rs , x);rs = 0,pushup(x);
}
int ans[M] , tp;
signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin >> n >> m;for(int i = 1;i <= n;i++)s[i] = 1 , h[i] = i;for(int i = 1;i <= m;i++){int u , v;cin >> u >> v;if(u > v)swap(u , v);e[i] = {u , v};}int ct = 0;sort(e + 1,e + m + 1);while(1){++ct;cin >> op[ct] >> u[ct] >> v[ct];if(op[ct] == -1)break;else if(op[ct] == 0){if(u[ct] > v[ct])swap(u[ct] , v[ct]);int x = u[ct] , y = v[ct];vis[lower_bound(e + 1,e + 1 + m,(edge){x , y}) - e] = 1;}}for(int i = 1;i <= m;i++)if(!vis[i]){merge(geth(e[i].u),geth(e[i].v));}for(int i = ct - 1;i >= 1;i--){int x = geth(u[i]) , y = geth(v[i]);if(op[i])split(x , y) , ans[++tp] = s[x] - 1;else merge(x,y);}while(tp)cout << ans[tp--] << '\n';return 0;
}

维护边权（生成树）

1. P4172 [WC2006] 水管局长

2. P4234 最小差值生成树

3. P2387 [NOI2014] 魔法森林 还没写，我先口胡一下，应该先将a排序，然后维护b的最小生成树

对于维护边权，我们这样做

link(e[i].id , e[i].u);
link(e[i].id , e[i].v);

同样的

cut(e[i].id , e[i].u);
cut(e[i].id , e[i].v);

维护子树信息

LCT 维护子树信息很无力。

我们可以维护虚子树信息，然后相应的 \(pushup\) 即可

P4219 [BJOI2014] 大融合