LCT学习笔记（不断更新ing）
先上♂例题
JZOJ2256. 【ZJOI2008】树的统计
Description
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。
我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身
Input
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
Output
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
Sample Input
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
Sample Output
4
1
2
2
10
6
5
6
5
16
Hint
【数据说明】
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
欸这不是树链剖分的例题吗
（关于树剖的资料自己找太水不写）
直接树剖+线段树维护
现在假设这棵树会以奇怪的方式变♂化，比如增加某条边或者删除某条边之类的
然后再求两点间的最大值/权值和
这题就会变得特别奇♂妙
于是有了lct
LCT
维护一个数据结构, 支持以下操作:
查询一个点的父亲
查询一个点所在的树的根
修改某个节点的权
向从某个节点到它所在的树的根的路径上的所有的节点的权增加一个数
查询从某个节点到它所在的树的根的路径上的所有的节点的权的最小值
把一棵树从某个节点和它的父亲处断开，使其成为两棵树
让一棵树的根成为另一棵树的某个节点的儿子，从而合并这两棵树
把某棵树的根修改为它的某个节点
查询在同一棵树上的两个节点的LCA
修改以某个节点为根的子树的所有节点的权
查询以某个节点为根的子树的所有节点的权的最小值
显然普通的树剖+线段树只能解决静态树类问题，因为线段树本身就不能删边/连边。
所以，只要把线段树换成某种动态数据结构就能解决了！
于是便有了
树剖+splay=动态树
splay学习笔记
正题
考虑用树剖的思想维护一棵树。
比如这样
然后在原树上分成一条条splay（注意此处的链并不是由节点多的儿子组成的）
LCT实际上是借鉴了树剖的思想，并不是按照子节点多的节点来作为重儿子，而是会随时改变。
申明一下概念
实边：对应树剖中的重边
虚边：对应树剖中的轻边
实链：对应树剖中的重链，每条实链用一颗splay来维护（对应树剖的线段树）
很显然每条重链只有splay的根有轻边向上连。
（因为按照树的定义，每个非根节点只有一个父亲，重链上的点的父亲就是splay中的父亲，所以只有splay的根节点才有轻边向上）
而splay的关键字是改点在原树中的深度
所以某个点的右子树都是深度比自己大的
所以上面的图实际上是这样分
然后经过splay的扭♂动后，可以变成这个样子（轻边无所谓，重边按照splay的顺序来放，这样更易懂）
（LCT实际上可以当作一个树形图来看，当前的根是谁并不重要）
显然，无论splay怎样扭♂动，原树都是不会变的
核心操作——access(x)
英文意思是“访问”当然为什么这么叫我也不知道
含义是使x向上到根的路径变成重链，之后x为该重链最深点
操作很简单，每次把当前x所在的点转到根，然后断掉右子树，在连上上一段作为右子树。
举个栗子
如此简单
code
{
int x;
x=0;
while (t)
{
splay(t);//旋到根
down2(t);//翻转标记
isroot[ch[t][1]]=1;//断开右子树，设为根
ch[t][1]=x;//连接上一段
isroot[x]=0;
tsum[t]=tsum[ch[t][0]]+tsum[ch[t][1]]+tr[t];
tmax[t]=max(max(tmax[ch[t][0]],tmax[ch[t][1]]),tr[t]);
x=t;
t=fa[t];
}
return;
}核心操作2——moveroot(x)
直译，把x变成当前LCT树的根（深度最小）。
显而易见，直接access(x)，然后splay到根。
因为access(x)后x的深度最大，所以直接翻转整颗树（lazy-tag）。
举个栗子
大概这样吧。。
code
void moveroot(int t)
{
access(t);//打通重链
splay(t);//旋转至根
rev[t]=1;//翻转整条链
down2(t);//下传标记
return;
}操作3——link(x,y)
在x和y之间连边。
moveroot(x)，然后从x向y连一条虚边。
（根据树的定义，当x为根时没有父亲，所以从x连向y，否则可能会冲掉y原来的父亲）
code
void link(int x,int y)
{
moveroot(x);
fa[x]=y;
return;
}操作4——cut(x,y)
断开除x和y之间的连边。
先moveroot(x)，然后access(y)。
因为x已经是LCT树的根（深度最浅），所以y一定在x的右子树。
断开x的右子树。
code
void cut(int x,int y)
{
moveroot(x);//把x变成根
access(y);//打通路径，之后y一定是x的右子树
splay(x);//保证x是当前树的根
isroot[y]=1;//断开右子树
fa[y]=0;
ch[x][1]=0;
tsum[x]=tsum[ch[x][0]]+tsum[ch[x][1]]+tr[x];
tmax[x]=max(max(tmax[ch[x][0]],tmax[ch[x][1]]),tr[x]);
return;
}操作5——getroot(x)
获得x所在splay的根。
一步步往上跳。
code
int getroot(int t)
{
while (!isroot[t])
t=fa[t];
return t;
}操作6——pd(x,y)
判断x、y是否连通
类似cut操作，打通从x到y的路径后判断根是否是另一方。
code
bool pd(int x,int y)
{
moveroot(x);
access(y);
splay(x);
if (getroot(y)==x)
return 1;
else
return 0;
}操作7、8——修改、查找
单点修改直接旋根然后修改。
区间修改直接取出一段后lazy-tag。
查找直接取出一段后找根节点，取根节点（可以在splay时记录下来）的信息。
代码就不放了。
模板题
随便口胡
给出n个点和m条边组成的森林，还有每个点初始权值。
给出q个询问，询问格式为Q x y
Q对应如下：
1 把x点权值修改为y
2 求x到y的最大值
3 求x到y的权值和
4 连接x、y
5 断开x、y间的连边
6 判断x、y是否连通
如果在操作过程中出现了奇♂妙的事情请输出”Fa♂Q”（不含引号）
code
瞎写
#include <iostream>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
using namespace std;
int max(int x,int y) {return (x>y?x:y);}
int II=400;
int a[1000001][2];
int tr[1000001];
int ch[1000001][2];
int fa[1000001];
bool isroot[1000001];
bool rev[1000001];
int flag[1000001];
int tsum[1000001];
int tmax[1000001];
int n,m,i,j,k,l,q,x,y;
char S[10];
bool bzzz;
void down(int t)
{
int i;
if (!t)
return;
if (flag[t]<(-999999))
return;
tr[t]=flag[t];
tsum[t]=tsum[ch[t][0]]+tsum[ch[t][1]]+tr[t];
tmax[t]=max(max(tmax[ch[t][0]],tmax[ch[t][1]]),tr[t]);
flag[t]=-1000000;
return;
}
void down2(int t)
{
int i;
if (rev[t])
{
rev[t]=0;
rev[ch[t][0]]=rev[ch[t][0]]^1;
rev[ch[t][1]]=rev[ch[t][1]]^1;
i=ch[t][0];
ch[t][0]=ch[t][1];
ch[t][1]=i;
}
return;
}
void left(int t)
{
int f;
f=fa[t];
down(f);
down(ch[f][0]);
down(ch[f][1]);
down(ch[t][0]);
down(ch[t][1]);
ch[f][1]=ch[t][0];
fa[ch[t][0]]=f;
if (isroot[f])
{
isroot[f]=0;
isroot[t]=1;
fa[t]=fa[f];
}
else
{
fa[t]=fa[f];
if (ch[fa[f]][0]==f)
ch[fa[f]][0]=t;
else
ch[fa[f]][1]=t;
}
ch[t][0]=f;
fa[f]=t;
tsum[f]=tsum[ch[f][0]]+tsum[ch[f][1]]+tr[f];
tmax[f]=max(max(tmax[ch[f][0]],tmax[ch[f][1]]),tr[f]);
tsum[t]=tsum[ch[t][0]]+tsum[ch[t][1]]+tr[t];
tmax[t]=max(max(tmax[ch[t][0]],tmax[ch[t][1]]),tr[t]);
return;
}
void right(int t)
{
int f;
f=fa[t];
down(f);
down(ch[f][0]);
down(ch[f][1]);
down(ch[t][0]);
down(ch[t][1]);
ch[f][0]=ch[t][1];
fa[ch[t][1]]=f;
if (isroot[f])
{
isroot[f]=0;
isroot[t]=1;
fa[t]=fa[f];
}
else
{
fa[t]=fa[f];
if (ch[fa[f]][0]==f)
ch[fa[f]][0]=t;
else
ch[fa[f]][1]=t;
}
ch[t][1]=f;
fa[f]=t;
tsum[f]=tsum[ch[f][0]]+tsum[ch[f][1]]+tr[f];
tmax[f]=max(max(tmax[ch[f][0]],tmax[ch[f][1]]),tr[f]);
tsum[t]=tsum[ch[t][0]]+tsum[ch[t][1]]+tr[t];
tmax[t]=max(max(tmax[ch[t][0]],tmax[ch[t][1]]),tr[t]);
if (bzzz)
look();
return;
}
void splay(int t)
{
int f,ff;
while (!isroot[t])
{
f=fa[t];
if (fa[f])
{
down2(fa[f]);
down2(ch[fa[f]][0]);
down2(ch[fa[f]][1]);
}
down2(f);
down2(ch[f][0]);
down2(ch[f][1]);
down2(t);
if (isroot[f])
{
if (ch[f][0]==t)
right(t);
else
left(t);
}
else
{
ff=fa[f];
if ((ch[ff][0]==f) && (ch[f][0]==t))
{
right(f);
right(t);
}
else
if ((ch[ff][0]==f) && (ch[f][1]==t))
{
left(t);
right(t);
}
else
if ((ch[ff][1]==f) && (ch[f][0]==t))
{
right(t);
left(t);
}
else
if ((ch[ff][1]==f) && (ch[f][1]==t))
{
left(f);
left(t);
}
}
}
return;
}
void access(int t)
{
int x;
x=0;
while (t)
{
splay(t);
down2(t);
isroot[ch[t][1]]=1;
ch[t][1]=x;
isroot[x]=0;
tsum[t]=tsum[ch[t][0]]+tsum[ch[t][1]]+tr[t];
tmax[t]=max(max(tmax[ch[t][0]],tmax[ch[t][1]]),tr[t]);
x=t;
t=fa[t];
}
return;
}
void moveroot(int t)
{
access(t);
splay(t);
rev[t]=1;
down2(t);
return;
}
int getroot(int t)
{
while (!isroot[t])
t=fa[t];
return t;
}
bool pd(int x,int y)
{
moveroot(x);
access(y);
splay(x);
if (getroot(y)==x)
return 1;
else
return 0;
}
void link(int x,int y)
{
moveroot(x);
if ((fa[x]==y) || (fa[y]==x))
printf("Fa♂Q\n");
else
fa[x]=y;
return;
}
void cut(int x,int y)
{
moveroot(x);
access(y);
splay(x);
if (ch[x][1])
{
isroot[y]=1;
fa[y]=0;
ch[x][1]=0;
}
else
printf("Fa♂Q\n");
tsum[x]=tsum[ch[x][0]]+tsum[ch[x][1]]+tr[x];
tmax[x]=max(max(tmax[ch[x][0]],tmax[ch[x][1]]),tr[x]);
return;
}
void change(int t,int s)
{
splay(t);
flag[t]=s;
down(t);
return;
}
void find(int x,int y,int z)
{
moveroot(x);
access(y);
splay(y);
if (!pd(x,y))
{
printf("Fa♂Q\n");
return;
}
if (!z)
printf("%d\n",tmax[y]);
else
printf("%d\n",tsum[y]);
return;
}
int main()
{
scanf("%d%d",&n,&m);
fo(i,1,m)
scanf("%d%d",&a[i][0],&a[i][1]);
tmax[0]=-1000000;
fo(i,1,n)
{
scanf("%d",&j);
tr[i]=j;
tsum[i]=j;
tmax[i]=j;
isroot[i]=1;
flag[i]=-1000000;
}
fo(i,1,m)
link(a[i][0],a[i][1]);
scanf("%d",&q);
printf("1.change 2.max 3.sum 4.link 5.cut 6.pd(liantong) \n");
fo(i,1,q)
{
scanf("%d%d%d",&j,&x,&y);
if (j==1)
change(x,y);
else
if (j==2)
find(x,y,0);
else
if (j==3)
find(x,y,1);
else
if (j==4)
link(x,y);
else
if (j==5)
cut(x,y);
else
if (j==6)
{
if (pd(x,y))
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}将近400行QwQ
例题解法
类似上面的模板题。
code
突然变短♂
#include <iostream>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(x,y) (x>y?x:y)
using namespace std;
int a[30001][2];
int tr[30001];
int ch[30001][2];
int fa[30001];
bool isroot[30001];
bool rev[30001];
int tsum[30001];
int tmax[30001];
int n,m,i,j,k,l,q,x,y,s;
char S[10];
inline int getint() { char c; int ret=0, k=1; for(c=getchar(); c<'0' || c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }
void up(int t)
{
tsum[t]=tsum[ch[t][0]]+tsum[ch[t][1]]+tr[t];
tmax[t]=max(max(tmax[ch[t][0]],tmax[ch[t][1]]),tr[t]);
}
void down2(int t)
{
if (rev[t])
{
rev[t]=0;
rev[ch[t][0]]^=1;
rev[ch[t][1]]^=1;
int i=ch[t][0];
ch[t][0]=ch[t][1];
ch[t][1]=i;
}
}
void rot(int t)
{
int f,x,y;
f=fa[t];
if (ch[f][1]==t)
x=1;else x=0;
y=x^1;
ch[f][x]=ch[t][y];
fa[ch[t][y]]=f;
if (isroot[f])
{
isroot[f]=0;
isroot[t]=1;
fa[t]=fa[f];
}
else
{
fa[t]=fa[f];
if (ch[fa[f]][y]==f)
ch[fa[f]][y]=t;
else
ch[fa[f]][x]=t;
}
ch[t][y]=f;
fa[f]=t;
up(f);
up(t);
}
void splay(int t)
{
int f;
while (!isroot[t])
{
f=fa[t];
if (fa[f])
down2(fa[f]);
down2(f);
down2(t);
if (isroot[fa[t]])
{rot(t);return;}
if ((ch[fa[f]][0]==f)^(ch[f][0]==t))
rot(t),rot(t);
else
rot(f),rot(t);
}
}
void access(int t)
{
s=0;
while (t)
{
splay(t);
down2(t);
isroot[ch[t][1]]=1;
ch[t][1]=s;
isroot[s]=0;
up(t);
s=t;
t=fa[t];
}
}
void moveroot(int t)
{
access(t);
splay(t);
rev[t]=1;
down2(t);
}
void link(int x,int y)
{
moveroot(x);
fa[x]=y;
}
void change(int t,int s)
{
splay(t);
tr[t]=s;
up(t);
}
void find(int x,int y,int z)
{
moveroot(x);
access(y);
if (!z)
printf("%d\n",tmax[s]);
else
printf("%d\n",tsum[s]);
}
int main()
{
n=getint();
m=n-1;
fo(i,1,m)
a[i][0]=getint(),a[i][1]=getint();
tmax[0]=-1000000;
fo(i,1,n)
{
j=getint();
tr[i]=tsum[i]=tmax[i]=j;
isroot[i]=1;
}
fo(i,1,m)
link(a[i][0],a[i][1]);
q=getint();
fo(i,1,q)
{
scanf("%s",S),x=getint(),y=getint();
switch(S[1]){
case 'H':change(x,y);break;
case 'M':find(x,y,0);break;
case 'S':find(x,y,1);break;}
}
return 0;
}例题2
Bzoj2049: [Sdoi2008]Cave 洞穴勘测
Description
辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。
Input
第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（”Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。
Output
对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）
Sample Input
样例输入1 cave.in
200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127
样例输入2 cave.in
3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3
Sample Output
样例输出1 cave.out
No
Yes
No
样例输出2 cave.out
Yes
No
HINT
数据说明 10%的数据满足n≤1000, m≤20000 20%的数据满足n≤2000, m≤40000 30%的数据满足n≤3000, m≤60000 40%的数据满足n≤4000, m≤80000 50%的数据满足n≤5000, m≤100000 60%的数据满足n≤6000, m≤120000 70%的数据满足n≤7000, m≤140000 80%的数据满足n≤8000, m≤160000 90%的数据满足n≤9000, m≤180000 100%的数据满足n≤10000, m≤200000 保证所有Destroy指令将摧毁的是一条存在的通道
这连权值都不用维护了。。。
直接连/删边，判断连通。
code
#include <iostream>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(x,y) (x>y?x:y)
using namespace std;
int tr[30001];
int ch[30001][2];
int fa[30001];
bool isroot[30001];
bool rev[30001];
int n,m,i,j,k,l,q,x,y,s;
char S[10];
inline int getint() { char c; int ret=0, k=1; for(c=getchar(); c<'0' || c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }
void down2(int t)
{
if (rev[t])
{
rev[t]=0;
rev[ch[t][0]]^=1;
rev[ch[t][1]]^=1;
int i=ch[t][0];
ch[t][0]=ch[t][1];
ch[t][1]=i;
}
}
void rot(int t)
{
int f,x,y;
f=fa[t];
if (ch[f][1]==t)
x=1;else x=0;
y=x^1;
ch[f][x]=ch[t][y];
fa[ch[t][y]]=f;
if (isroot[f])
{
isroot[f]=0;
isroot[t]=1;
fa[t]=fa[f];
}
else
{
fa[t]=fa[f];
if (ch[fa[f]][y]==f)
ch[fa[f]][y]=t;
else
ch[fa[f]][x]=t;
}
ch[t][y]=f;
fa[f]=t;
}
void splay(int t)
{
int f;
while (!isroot[t])
{
f=fa[t];
if (fa[f])
down2(fa[f]);
down2(f);
down2(t);
if (isroot[fa[t]])
{rot(t);return;}
if ((ch[fa[f]][0]==f)^(ch[f][0]==t))
rot(t),rot(t);
else
rot(f),rot(t);
}
}
void access(int t)
{
s=0;
while (t)
{
splay(t);
down2(t);
isroot[ch[t][1]]=1;
ch[t][1]=s;
isroot[s]=0;
s=t;
t=fa[t];
}
}
void moveroot(int t)
{
access(t);
splay(t);
rev[t]=1;
down2(t);
}
void link(int x,int y)
{
moveroot(x);
fa[x]=y;
}
void cut(int x,int y)
{
moveroot(x);
access(y);
splay(x);
ch[x][1]=0;
isroot[y]=1;
fa[y]=0;
}
int getroot(int t)
{
while (!isroot[t])
t=fa[t];
return t;
}
void pd(int x,int y)
{
moveroot(x);
access(y);
splay(x);
if (getroot(y)==x)
printf("Yes\n");
else
printf("No\n");
return;
}
int main()
{
n=getint();
q=getint();
fo(i,1,n)
isroot[i]=1;
fo(i,1,q)
{
scanf("%s",S),x=getint(),y=getint();
switch(S[1]){
case 'o':link(x,y);break;
case 'e':cut(x,y);break;
case 'u':pd(x,y);break;}
}
return 0;
}后记
各位大佬将就着看吧。。。
学♂习资料：
【动态树】【Link Cut Tree】动态树的理解（入门）
动态树之LCT(link-cut tree)讲解
link-cut tree
LCT ——学习笔记
LCT 讲解 动态树的基本使用
LCT动态树学习小记
下一篇： php如何使用session？