这个东西欠了很久了(博客也停了很久了)
这篇博文不负责讲解Lct的基础知识（太麻烦）所以有需要的同学可以看这里
PART 1
我们首先给一个模板
struct Splay{int F,s[2],rev;int val,sum;inline void NewNode(int fa,int x){F=fa; s[0]=s[1]=rev=0;val=sum=x; return ;}
}tree[Maxn];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void Pushup(int v){tree[v].sum=tree[tree[v].s[0]].sum+tree[v].val+tree[tree[v].s[1]].sum; return ;}
inline void Rev(int v){tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}
inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}
inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}
inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}
inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) Set(g,v,t2); else tree[v].F=g;Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;
}
inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;
}
inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F) Splay(v),tree[v].s[1]=u,Pushup(v); return ;}
inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}
inline void Split(int v,int u){Make_Root(v); Access(u); Splay(u); return ;}
inline void Link(int v,int u){Make_Root(v); tree[v].F=u; return ;}
inline void Cut(int v,int u){Split(v,u); tree[u].s[0]=tree[v].F=0; Pushup(u); return ;}
inline void Change(int v,int x){Splay(v); tree[v].val=x; Pushup(v); return ;}
inline void Ask(int v,int u){Split(v,u); cout<<tree[u].sum<<'\n'; return ;}
inline int Get_Root(int v){Splay(v); Access(v); Pushdown(v); while(tree[v].s[0]) v=tree[v].s[0],Pushdown(v); return v;
}啊，确实丑的不行，但是打起来很省时间。结构体的效率也还不错。
有一个常见问题，那就是GetRoot的时候是否需要pushdown
如果只是简单的判断连通性那么是不需要的。但是如果一定要找真正的root的话就要pushdown(结构问题)
我们干脆来看一个常见的Link-Cut tree例题。
【BZOJ3282】Tree
Description
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是连通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到y已经连通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点x上的权值变成y。
Input
第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。
第２行到第Ｎ＋１行，每行一个整数，整数在［1，10^9］内，代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。
Output
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
Sample Input
3 3 1231 1 20 1 2 0 1 1
Sample Output
31
Hint
1<=N,M<=300000
直接上板子233
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=300005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
struct Splay{int F,s[2],rev;int val,mul;inline void NewNode(int fa,int x){F=fa; s[0]=s[1]=rev=0;val=mul=x; return ;}
}tree[Maxn];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void Pushup(int v){tree[v].mul=tree[tree[v].s[0]].mul^tree[v].val^tree[tree[v].s[1]].mul; return ;}
inline void Rev(int v){if(v==0) return ; tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}
inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}
inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}
inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}
inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; tree[v].F=g;Set(v,p,t1^1); Set(p,S,t1); Pushup(p); return ;
}
inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;
}
inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F) Splay(v),tree[v].s[1]=u,Pushup(v); return ;}
inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}
inline void Split(int v,int u){Make_Root(v); Access(u); Splay(u); return ;}
inline void Link(int v,int u){Make_Root(v); tree[v].F=u; return ;}
inline void Cut(int v,int u){Split(v,u); tree[u].s[0]=tree[v].F=0; Pushup(u); return ;}
inline int Get_Root(int v){Access(v); Splay(v); while(tree[v].s[0]) Pushdown(v),v=tree[v].s[0]; return v;}
inline void Ask(int v,int u){Split(v,u); cout<<tree[u].mul<<'\n'; return ;}
inline void Change(int v,int x){Splay(v); tree[v].val=x; Pushup(v); return ;}
int main(){int n=read(),m=read();for(int i=1;i<=n;i++) tree[i].NewNode(0,read());for(int i=1;i<=m;i++){int f=read(),x=read(),y=read();if(f==0) Ask(x,y);else if(f==1){if(Get_Root(x)!=Get_Root(y)) Link(x,y); }else if(f==2){if(Get_Root(x)==Get_Root(y)) Cut(x,y);}else Change(x,y);}return 0;
}然后Lct可以维护一些边权的问题。为了方便起见(拒绝仙人掌)我们直接新建节点代表边
【BZOJ4668】冷战
Description
怎样维护最早的联通性呢？
直接一点，每一条加边我们都给它赋予一条边权，大小为当前时间。
然后我们直接维护链上的最大值即可
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){char c;int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9')rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m;
struct Lct_Tree{int F,s[2],val,rev,maxx;inline void NewNode(int fa,int x){F=fa;val=maxx=x;s[0]=s[1]=rev=0;return ;}
}tree[1000005];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void Pushup(int v){tree[v].maxx=max(tree[tree[v].s[0]].maxx,max(tree[v].val,tree[tree[v].s[1]].maxx));return ;}
inline void Rev(int v){if(v==0)return ;tree[v].rev^=1;swap(tree[v].s[0],tree[v].s[1]);return ;}
inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]);Rev(tree[v].s[1]);tree[v].rev=0;}return ;}
inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}
inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}
inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) Set(g,v,t2); else tree[v].F=g;Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;
}
inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;
}
inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F) Splay(v),tree[v].s[1]=u,Pushup(v); return ;}
inline void Make_Root(int v){Access(v);Splay(v);Rev(v);return ;}
inline void Link(int v1,int v2){Make_Root(v1);tree[v1].F=v2;return ;}
inline int Ask(int v1,int v2){Make_Root(v1);Access(v2);Splay(v2);return tree[v2].maxx;}
inline int Find_Root(int v){while(tree[v].F)v=tree[v].F;return v;}
int main(){n=read();m=read();int last=0,cnt=0;for(int i=1;i<=m;i++){int f=read(),x=read()^last,y=read()^last;int fx=Find_Root(x),fy=Find_Root(y);if(f==0){cnt++;if(fx!=fy){tree[n+cnt].NewNode(0,cnt);Link(x,n+cnt);Link(y,n+cnt);}}else {if(fx!=fy)cout<<0<<'\n',last=0;else last=Ask(x,y),cout<<last<<'\n';}}return 0;
}事实上，只有加边的问题多数时候可以用启发式合并的并查集维护。
时限1s，在TLE的边缘试探
bzoj表现一般
PART 2
由此，我们发现Lct显然可以维护最小生成树
【WC2006】水管局长是一道显然的例题
所以我们来看一道更难的(笑)
【HNOI2010】城市建设
Description
PS国是一个拥有诸多城市的大国，国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，Louis会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和， Louis决定求助于你来完成这个任务。
Input
文件第一行包含三个整数N,M,Q，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。
接下来M行，第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi,Yi≤n, 0≤Zi≤50000000)，表示在城市Xi与城市Yi之间修建道路的代价为Zi。
接下来Q行，每行包含两个数k,d，表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。
Output
输出包含Q行，第i行输出得知前i条消息后使城市连通的最小花费总和。
Sample Input
5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3
Sample Output
14
10
9
Hint
对于20%的数据, n≤1000,m≤6000,Q≤6000。
有20%的数据，n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。
对于100%的数据, n≤20000,m≤50000,Q≤50000。
这个emm
网上好像到处都是CDQ重构图的代码，但是我不会CDQ怎么办qwq？
我们发现了修改的操作(一个修改显然可以看做是一个删除和一个添加)，所以lct不能够直接维护了，怎么办？
我们有一个神奇的东西叫做线段树分治。。。这玩意儿用一个log的代价把删除变成了添加(说得不对轻喷)
然后用一个栈记下lct的操作，撤销的时候link变cut，cut变link就好了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int Maxn=50005,Maxm=80005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m,Q;
int tot;
struct Edge {int a,b,val;} e[Maxm<<1];
struct node {int id,pos;} opt[Maxm];
namespace Lct{long long ans=0;int top;struct STACK{int id,opt;}S[Maxm];struct Splay{int F,s[2],rev;int id,mxid;} tree[Maxn+(Maxm<<1)];inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}inline void Emax(int v,int u){if(e[tree[v].mxid].val<e[tree[u].mxid].val) tree[v].mxid=tree[u].mxid; return ;}inline void Pushup(int v){tree[v].mxid=tree[v].id; Emax(v,tree[v].s[0]); Emax(v,tree[v].s[1]); return ;}inline void Rev(int v){if(v==0) return ; tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; tree[v].F=g;Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;}inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;}inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F) Splay(v),tree[v].s[1]=u,Pushup(v); return ;}inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}inline void Split(int v,int u){Make_Root(v); Access(u); Splay(u); return ;}inline void Link(int v,int u){Make_Root(v); tree[v].F=u; return ;}inline void Cut(int v,int u){Split(v,u); tree[u].s[0]=tree[v].F=0; Pushup(u); return ;}inline int Get_Root(int v){Access(v); Splay(v); while(tree[v].s[0]) v=tree[v].s[0]; return v;}inline int Ask(int v,int u){Split(v,u); return tree[u].mxid;}inline void Sov(int id){int a=e[id].a,b=e[id].b;if(Get_Root(a)==Get_Root(b)){int pid=Ask(a,b);if(e[id].val<e[pid].val){Cut(e[pid].a,n+pid); Cut(e[pid].b,n+pid);Link(a,n+id); Link(b,n+id);S[++top]=(STACK){pid,0}; ans-=e[pid].val; S[++top]=(STACK){id,1}; ans+=e[id].val;}}else{Link(a,n+id); Link(b,n+id);ans+=e[id].val; S[++top]=(STACK){id,1};}return ;}inline void Undo(int lim){while(top>lim){int id=S[top].id,opt=S[top].opt;--top;if(opt==0) Link(e[id].a,n+id),Link(e[id].b,n+id),ans+=e[id].val;else Cut(e[id].a,n+id),Cut(e[id].b,n+id),ans-=e[id].val;} return ;}
}
namespace Sgt{struct Segment_Tree{int L,R;vector<int> id;}tree[Maxm<<1];void Build(int v,int L,int R){tree[v].L=L; tree[v].R=R;if(L==R) return ;int mid=(L+R)>>1;Build(v<<1,L,mid); Build(v<<1|1,mid+1,R);return ;}void Cover(int v,int L,int R,int x){if(tree[v].L>R||tree[v].R<L) return ;if(L<=tree[v].L&&tree[v].R<=R) {tree[v].id.push_back(x);return ;}Cover(v<<1,L,R,x); Cover(v<<1|1,L,R,x); return ;}void Sov(int v){int top=Lct::top;for(int i=0;i<tree[v].id.size();++i)Lct::Sov(tree[v].id[i]);if(tree[v].L==tree[v].R){cout<<Lct::ans<<'\n';Lct::Undo(top);return ;}Sov(v<<1); Sov(v<<1|1); Lct::Undo(top);return ; }
}
int main(){n=read(); m=read(); Q=read(); tot=m;for(int i=1;i<=m;++i){e[i].a=read(); e[i].b=read(); e[i].val=read();opt[i].id=i; opt[i].pos=1; Lct::tree[n+i].id=i;}Sgt::Build(1,1,Q);for(int i=1;i<=Q;++i){int id=read(),x=read();e[++tot]=e[id]; e[tot].val=x; Lct::tree[n+tot].id=tot;Sgt::Cover(1,opt[id].pos,i-1,opt[id].id);opt[id].id=tot; opt[id].pos=i;}for(int i=1;i<=m;++i)Sgt::Cover(1,opt[i].pos,Q,opt[i].id);e[0].val=-1;Sgt::Sov(1);return 0;
}写得太丑TLE了
（BZOJ就更不用说，只有本校OJ能够安慰我的心灵）
然后，类似的题目还有
【bzoj4736/uoj#274】[清华集训2016]温暖会指引我们前行
(其实很多题目维护的lct都是为了其他部分做准备来着)
/*****************************************************我是善良的分割线************************************************/
PART 3
lct的操作 ：
双联通分量
最长链
二分图
联通块个数
重心
后缀自动机
……
Lct还有很多奇怪的操作。比如维护双联通分量
（众所周知）一张无向连通图缩点之后会形成一颗树的结构。那么我们就可以在一个不断加边的图中使用LCT维护点双分量了。
【BZOJ2959】长跑
Description
某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”，同学们纷纷离开寝室，离开教室，离开实验室，到操场参加3000米长跑运动。一时间操场上熙熙攘攘，摩肩接踵，盛况空前。
为了让同学们更好地监督自己，学校推行了刷卡机制。
学校中有n个地点，用1到n的整数表示，每个地点设有若干个刷卡机。
有以下三类事件：
1、修建了一条连接A地点和B地点的跑道。
2、A点的刷卡机台数变为了B。
3、进行了一次长跑。问一个同学从A出发，最后到达B最多可以刷卡多少次。具体的要求如下：
当同学到达一个地点时，他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次，即使多次到达同一地点也不能多次刷卡。
为了安全起见，每条跑道都需要设定一个方向，这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向，按照任意路径从A地点到B地点能刷卡的最多次数。
Input
输入的第一行包含两个正整数n,m，表示地点的个数和操作的个数。
第二行包含n个非负整数，其中第i个数为第个地点最开始刷卡机的台数。
接下来有m行，每行包含三个非负整数P,A,B，P为事件类型，A,B为事件的两个参数。
最初所有地点之间都没有跑道。
每行相邻的两个数之间均用一个空格隔开。表示地点编号的数均在1到n之间，每个地点的刷卡机台数始终不超过10000，P=1,2,3。
Output
输出的行数等于第3类事件的个数，每行表示一个第3类事件。如果该情况下存在一种设定跑道方向的方案和路径的方案，可以到达，则输出最多可以刷卡的次数。如果A不能到达B，则输出-1。
Sample Input
9 31
10 20 30 40 50 60 70 80 90
3 1 2
1 1 3
1 1 2
1 8 9
1 2 4
1 2 5
1 4 6
1 4 7
3 1 8
3 8 8
1 8 9
3 8 8
3 7 5
3 7 3
1 4 1
3 7 5
3 7 3
1 5 7
3 6 5
3 3 6
1 2 4
1 5 5
3 3 6
2 8 180
3 8 8
2 9 190
3 9 9
2 5 150
3 3 6
2 1 210
3 3 6
Sample Output
-1
-1
80
170
180
170
190
170
250
280
280
270
370
380
580
Hint
【数据规模及约定】
对于100%的数据，m<=5n，任意时刻，每个地点的刷卡机台数不超过10000。N<=1.5×10^5
如果没有动态加边和，我们完全可以Tarjan一次之后在树上操作一番。
那么现在怎么办？
简单来说，两个并查集分别维护所属联通块和联通块是否会成为新的大联通块
对于新加的非树边，就可以把这一条链缩成一个块。
然后统计权值之和就可以了。
/****代码丢失****/
我们lct还可以维护最长链。
首先，在不带边权的树上，最长链就是直径的长度。
关于直径有这样两个性质：
1、从树中任意一点开始能够遍历到的最远点一定是直径的端点
2、两颗树合并，则新树的最长链的端点一定来源于原来的四个端点的其二
我们利用这个性质就可以用lct维护最长链了。
远行
Description
Miranda 生活的城市有 N个小镇，一开始小镇间没有任何道路连接。随着经济发现，小镇之间陆续建起了一些双向的道路但是由于经济不太发达，在建设过程中，会保证对于任意两个小镇，最多有一条路径能互相到达。有的时候 Miranda 会从某个小镇开始进行徒步旅行，每次出发前，她都想选择一个她能到达的最远的小镇作为终点，并且她在行走过程中是不会走回头路的，为了估算这次旅行的时间，她会需要你告诉她这次旅行的时间会是多少呢？可以假设通过每条道路都需要单位时间，并且 Miranda 不会在小镇停留。
Input
第一行一个整数 type，表示数据类型。
第二行两个整数 N、Q。
接下来 Q 行，每行先读入一个整数 t，若 t=1，则接下来读入两个整数 u、v，表示小镇 u与小镇 v 建立了一条新道路。若 t=2，读入一个整数 u，表示 Miranda 要开始一次从小镇 u出发的旅行。
若 type=1，记 lastAns表示最近一次 Miranda 旅行的时间，那么对于每次操作的 u或 u,v，都要异或上 lastAns。
若 type=0，则不需要对数据进行处理。
Output
对于每次询问，输出 Miranda 能到达的最远的小镇的距离是多少。注意 Miranda 可能只能留在开始的小镇。
Sample Input
0
5 10
1 4 5
2 3
2 5
2 1
1 5 3
1 1 4
2 3
2 5
1 5 2
2 1
Sample Output
0
1
0
3
2
3
Hint
【数据范围及约定】
对于 20%的数据，N≤5000,Q≤10000；
对于 50%的数据，N≤100000,Q≤200000；
对于另外 20%的数据，type=0；
对于 100%的数据，N≤300000,Q≤500000,type∈{0,1}，解密后的 u、v满足 1≤u,v≤N，且道路的修建会满足：每一时刻，都不存在 u,v 使得 u,v之间能通过多种方式到达。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=300005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m,type,last;
int fa[Maxn];
inline int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
struct Position {int a,b,len;} Pos[Maxn];
namespace Lct{struct Splay{int F,s[2],rev,size;inline void Rev(){rev^=1; swap(s[0],s[1]); return ;}}tree[Maxn];inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}inline void Pushup(int v){tree[v].size=tree[tree[v].s[0]].size+1+tree[tree[v].s[1]].size; return ;}inline void Pushdown(int v){if(tree[v].rev){tree[tree[v].s[0]].Rev(); tree[tree[v].s[1]].Rev(); tree[v].rev=0;} return ;}inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; tree[v].F=g;Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;}inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;}inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F) Splay(v),tree[v].s[1]=u,Pushup(v); return ;}inline void Make_Root(int v){Access(v); Splay(v); tree[v].Rev(); return ;}inline void Split(int v,int u){Make_Root(v); Access(u); Splay(u); return ;}inline void Link(int v,int u){Make_Root(v); tree[v].F=u; return ;}inline int Ask(int v,int u){Split(v,u); return tree[u].size-1;}inline void Sov(int v,int u){int fx=getfa(v),fy=getfa(u);fa[fx]=fy; Link(v,u);int a=Pos[fx].a,b=Pos[fx].b,c=Pos[fy].a,d=Pos[fy].b;int x=a,y=b,maxx=Pos[fx].len,temp;if(maxx<Pos[fy].len) {maxx=Pos[fy].len; x=c; y=d;}temp=Ask(a,c); if(maxx<temp){maxx=temp; x=a; y=c;}temp=Ask(a,d); if(maxx<temp){maxx=temp; x=a; y=d;}temp=Ask(b,c); if(maxx<temp){maxx=temp; x=b; y=c;}temp=Ask(b,d); if(maxx<temp){maxx=temp; x=b; y=d;}Pos[fy].a=x; Pos[fy].b=y; Pos[fy].len=maxx;return ;}
}
int main(){type=read();n=read(); m=read();for(int i=1;i<=n;i++){fa[i]=i; Lct::tree[i].size=1;Pos[i].a=Pos[i].b=i;Pos[i].len=0;}for(int i=1;i<=m;i++){int f=read();if(f==1){int x=read(),y=read();if(type) x^=last,y^=last;Lct::Sov(x,y);}else {int x=read(); if(type) x^=last;int p=getfa(x);last=max(Lct::Ask(x,Pos[p].a),Lct::Ask(x,Pos[p].b));cout<<last<<'\n';}}return 0;
}lct还可以维护二分图。
根据二分图的定义，如果一张图中出现了基环(简单来说，就是奇数个节点的环)
【BZOJ4025】二分图
Description
神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。
Input
输入数据的第一行是三个整数n,m,T。
第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这条边在start时刻出现，在第end时刻消失。
Output
输出包含T行。
在第i行中，如果第i时间段内这个图是二分图，那么输出“Yes”，否则输出“No”，不含引号。
Sample Input
3 3 3
1 2 0 2
2 3 0 3
1 3 1 2
Sample Output
Yes
No
Yes
Hint
【样例说明】
0时刻，出现两条边1-2和2-3。
第1时间段内，这个图是二分图，输出Yes。
1时刻，出现一条边1-3。
第2时间段内，这个图不是二分图，输出No。
2时刻，1-2和1-3两条边消失。
第3时间段内，只有一条边2-3，这个图是二分图，输出Yes。
【数据范围】
n<=100000，m<=200000，T<=100000，1<=u,v<=n，0<=start<=end<=T。
对于一条边，我们将它的边权赋为消失的时间，然后维护一颗关于时间的最大生成树。
如果一条边加上之后使得当前图存在基环，那么只要这条边存在则不为二分图。
我们考虑将这个时间变短(也就是使边的存在时间变短)，可以将当前环上权值最小的边用当前边替换，则被替换边的存在时间就是不为二分图的最短时间。(这是由最大生成树决定的)。
对于树边，删除它显然不会影响二分图的性质(没有要求二分图一定联通)
对于基环边，简单的将它从基环边的集合中移去即可。二分图存在的充要条件就是基环边集合为空。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=100005,Maxm=200005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m,T;
struct Edge {int a,b,val;} e[Maxm];
int cnt,on[Maxm],off[Maxm];
struct Opt {int t,id,type;} opt[Maxm<<1];
inline bool cmp(Opt A,Opt B){return A.t<B.t;}
namespace Lct{struct Splay{int F,s[2],rev;int id,mnid,size,d;inline void NewNode(int x){F=s[0]=s[1]=rev=0;id=mnid=x; size=d=1; return ;}}tree[Maxn+Maxm];inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}inline void Emin(int v,int u){if(e[tree[v].mnid].val>e[tree[u].mnid].val) tree[v].mnid=tree[u].mnid; return ;}inline void Pushup(int v){tree[v].mnid=tree[v].id; Emin(v,tree[v].s[0]); Emin(v,tree[v].s[1]);tree[v].size=tree[tree[v].s[0]].size+tree[v].d+tree[tree[v].s[1]].size;return ;}inline void Rev(int v){if(v==0) return ; tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; tree[v].F=g;Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;}inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;}inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F) Splay(v),tree[v].s[1]=u,Pushup(v); return ;}inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}inline void Split(int v,int u){Make_Root(v); Access(u); Splay(u); return ;}inline void Link(int v,int u){Make_Root(v); tree[v].F=u; return ;}inline void Cut(int v,int u){Split(v,u); tree[u].s[0]=tree[v].F=0; Pushup(u); return ;}inline int Get_Root(int v){Access(v); Splay(v); while(tree[v].s[0]) Pushdown(v),v=tree[v].s[0]; return v;}inline int Ask(int v,int u){Split(v,u); return tree[u].mnid;}inline void Sov(int id,int f){int a=e[id].a,b=e[id].b;if(f==1){if(a==b){on[id]=0; off[id]=1; ++cnt; return ;}if(Get_Root(a)==Get_Root(b)){int pid=Ask(a,b),Sz=tree[b].size;if(e[id].val>e[pid].val){if(Sz&1) off[pid]=1,++cnt;Cut(e[pid].a,n+pid); Cut(e[pid].b,n+pid);Link(a,n+id); Link(b,n+id);on[pid]=0; on[id]=1;}else if(Sz&1){ on[id]=0; off[id]=1; ++cnt;}}else Link(a,n+id),Link(b,n+id),on[id]=1;}else {if(on[id]) Cut(a,n+id),Cut(b,n+id);else if(off[id]) --cnt;}return ;}
}
int main(){n=read(); m=read(); T=read();for(int i=1;i<=n;i++) Lct::tree[i].NewNode(0);for(int i=1;i<=m;i++){e[i].a=read(); e[i].b=read(); Lct::tree[n+i].id=Lct::tree[n+i].mnid=i;int st=read(),ed=read(); e[i].val=ed;opt[(i<<1)-1]=(Opt){st,i,1};opt[(i<<1)]=(Opt){ed,i,0};} sort(opt+1,opt+1+(m<<1),cmp);e[0].val=0x3f3f3f3f;for(int i=1,p=1;i<=T;i++){while(opt[p].t<i&&p<=m<<1) Lct::Sov(opt[p].id,opt[p].type),++p;puts(cnt?"No":"Yes");}return 0;
}lct还可以维护联通块的个数
首先，我们可以维护图的生成树。
如果新加的边在是横叉边或者返祖边，也就是说在原来的生成树结构中形成了环，那么不会对联通块的个数产生影响。
如果连接的两个联通块本来不联通，那么就会使总的联通块数量减一。
【BZOJ3514】GERALD07加强版
Description
N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。
Input
第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。
接下来M行，代表图中的每条边。
接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。
Output
K行每行一个整数代表该组询问的联通块个数。
Sample Input
3 5 4 0
1 3
1 2
2 1
3 2
2 2
2 3
1 5
5 5
1 2
Sample Output
2
1
3
1
Hint
对于100%的数据，1≤N、M、K≤200,000。
那么对于这个问题，我们维护一颗以时间为权值的最大生成树。
对于新加入的边，如果有弹出边，则这条边和弹出边两者随便少一条都不会对联通块造成影响。
对于当前的询问[L,R]，如果弹出边的时间小于R，则当前边加入之后会使得原图减少一个联通块。
没有弹出边的情况显然会减少联通块的个数。
所以说我们就用lct维护每一条边加入之后弹出边的时间，然后对于一次询问就相当于询问这个区间弹出边时间小于L的边的个数。这些边都会使得原图的联通块-1。原图联通块的总个数最开始是n个。
询问边的个数我们考虑使用主席树解决。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=200005;
const int Inf=0x3f3f3f3f;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m,K,type,last,a[Maxn];
struct Edge {int a,b;} e[Maxn];
namespace Lct{struct Splay{int F,s[2],rev;int id,mnid;inline void NewNode(int x){F=s[0]=s[1]=rev=0;id=mnid=x; return ;}}tree[Maxn<<1];inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}inline void Pushup(int v){tree[v].mnid=min(tree[v].id,min(tree[tree[v].s[0]].mnid,tree[tree[v].s[1]].mnid));return;}inline void Rev(int v){if(v==0) return ; tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; tree[v].F=g;Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;}inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;}inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F) Splay(v),tree[v].s[1]=u,Pushup(v); return ;}inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}inline void Split(int v,int u){Make_Root(v); Access(u); Splay(u); return ;}inline void Link(int v,int u){Make_Root(v); tree[v].F=u; return ;}inline void Cut(int v,int u){Split(v,u); tree[u].s[0]=tree[v].F=0; Pushup(u); return ;}inline int Get_Root(int v){Access(v); Splay(v); while(tree[v].s[0]) Pushdown(v),v=tree[v].s[0]; return v;}inline int Ask(int v,int u){Split(v,u); return tree[u].mnid;}
}
namespace Sgt{#define mid ((L+R)>>1)int root[Maxn],ind=0;struct Persistent_Segment_Tree{int s[2],d;}tree[Maxn*30];inline void Insert(int &v,int p,int L,int R,int pos){v=++ind; tree[v].d=tree[p].d+1;if(L==R) return ;int f=(pos>mid); f?L=mid+1:R=mid;tree[v].s[!f]=tree[p].s[!f];Insert(tree[v].s[f],tree[p].s[f],L,R,pos);return ;}inline int Ask(int x,int y,int L,int R,int lim){if(L>lim) return 0;if(R<=lim) return tree[y].d-tree[x].d;return Ask(tree[x].s[0],tree[y].s[0],L,mid,lim)+Ask(tree[x].s[1],tree[y].s[1],mid+1,R,lim);}
}
int main(){n=read(); m=read(); K=read(); type=read();for(int i=0;i<=n;i++) Lct::tree[i].mnid=Lct::tree[i].id=Inf;for(int i=1;i<=m;i++){int x=read(),y=read();e[i].a=x; e[i].b=y;if(x==y){a[i]=i; continue;}Lct::tree[n+i].NewNode(i);if(Lct::Get_Root(x)==Lct::Get_Root(y)){int id=Lct::Ask(x,y);a[i]=id;Lct::Cut(e[id].a,n+id); Lct::Cut(e[id].b,n+id);Lct::Link(x,n+i); Lct::Link(y,n+i);}else {a[i]=0;Lct::Link(x,n+i); Lct::Link(y,n+i);}}for(int i=1;i<=m;i++) Sgt::Insert(Sgt::root[i],Sgt::root[i-1],0,m,a[i]);for(int i=1;i<=K;i++){int x=read(),y=read();if(type) x^=last,y^=last;last=n-Sgt::Ask(Sgt::root[x-1],Sgt::root[y],0,m,x-1);cout<<last<<'\n';}return 0;
}维护重心这个东西我们先略过，后面维护子树信息时再说。
然后Lct的结构在其他地方也很有用。后缀自动机就是其中一个。
后缀自动机的fail树在构建过程中会有多次的link-cut操作，如果题目要在插入过程中询问right集合的大小的话，lct就是不错的选择。
【BZOJ4545】DQS的trie
Description
DQS的自家阳台上种着一棵颗粒饱满、颜色纯正的trie。
DQS的trie非常的奇特，它初始有n0个节点，n0-1条边，每条边上有一个字符。并且，它拥有极强的生长力：某个i时刻，某个节点就会新生长出一颗子树，它拥有si个节点且节点之间的边上有一个字符，并且新生长出来的子树也是一个树结构。然而因为是新长出来的，根据生活常识可知si必定不会大于i时刻之前的树的大小。
DQS定义trie的子串为从根节点（1号节点）往下走到所有节点所构成的字符串的所有的后缀。DQS身为一个单身doge，常常取出其中一个子串送给妹子，然而他并不希望送给妹子两个相同的子串，所以他非常关心当前trie的本质不同的子串数目。
DQS有时还会去商店购买子串，若他在商店看上某个子串，他希望得知这个子串是否在自家阳台的trie上已经出现，若出现则出现了多少次。如果出现了，他就可以直接回家取trie上的子串辣！
然而DQS身为一个蒟蒻，看着自家阳台的trie树一天天在长大，他被如此众多的节点弄得眼花缭乱，于是他找到了IOI2016Au的你。他会告诉你自家trie树的成长历程，他希望你能够对于每一次询问都做出正确回复。
Input
第一行输入一个整数id，代表测试点编号。
接下来一行输入一个整数n0，表示初始树的大小。
接下来n0-1行，每行两个整数u,v和一个字符c，表示u号节点和v号节点之间有一条边，边上的字母为c。
接下来输入m表示有m组操作。
对于每一组，第一行输入一个整数opt。
若opt=1，则是一组询问，询问当前trie的本质不同的子串数目是多少。
若opt=2，则后面跟两个整数rt,si，表示以点rt为根向下长出一个子树，大小为si。
接下来si-1行，每行两个整数u,v和一个字符c，表示u号节点和v号节点之间有一条边，边上的字母为c。若长出子树之前当前树的大小是n，则这si-1点的编号分别为n+1,n+2…n+si-1。
若opt=3，则是一组询问，后面输入一个字符串S，询问字符串S在当前trie中的出现次数。
Output
对于每个opt=1或3，输出一行表示答案。
Sample Input
1
4
1 2 a
1 3 b
2 4 b
6
1
2 2 4
2 5 b
2 6 c
5 7 b
1
3 ab
2 6 3
6 8 a
6 9 b
1
Sample Output
3
7
2
11
Hint
【数据范围及提示】
第一个询问，本质不同的子串是 a,b,ab。
第二个询问，本质不同的子串是 a,b,c,ab,ac,bb,abb。
第三个询问，ab出现次数是 2。
第四个询问，本质不同的子串是 a,b,c,ab,ac,ca,cb,bb,abb,aca,acb。
opt=1或3时对原树不做修改，只是询问。
每次opt=2，会增加si-1个节点，因为有一个节点是原树上作为新树的根出现的。
数据中，对于链的部分分，满足端点为根节点，每次新建子树都从尾部插入。
对于全部数据，保证从始至终每条边上的字符均为小写字母’a’或’b’或’c’。
n是最终树的大小,N<=100000,M<=100000,Si<=当前树的大小
额。。。根据题目的要求直接做就行了。
本质不同的子串个数在插入过程中就可以直接维护，询问出现次数就找到对应的状态的size大小即可。
这个过程中我们的广义后缀自动机用lct来维护fail树
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=100005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
inline int cread(){char c; while((c=getchar())!='a'&&c!='b'&&c!='c'); return c-'a';}
int n,m;
long long ans;
char ssr[Maxn];
namespace Lct{struct Splay{int F,s[2],add,size;}tree[Maxn<<1];inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}inline void Add(int v,int x){if(v==0) return ; tree[v].add+=x; tree[v].size+=x; return ;}inline void Pushdown(int v){if(tree[v].add){Add(tree[v].s[0],tree[v].add); Add(tree[v].s[1],tree[v].add); tree[v].add=0;} return ;}void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; tree[v].F=g;Set(v,p,!t1); Set(p,S,t1); return ;}void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p))Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} return ;}inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F) Splay(v),tree[v].s[1]=u; return ;}inline void Link(int v,int p){tree[v].F=p; Access(p); Splay(p); Add(p,tree[v].size); return ;}inline void Cut(int v){Access(v); Splay(v); Add(tree[v].s[0],-tree[v].size); tree[tree[v].s[0]].F=0; tree[v].s[0]=0; return ;}
}
namespace Sam{const int N=Maxn<<1;int root,cnt,last[Maxn];int s[N][3],mx[N],fail[N];inline void Reset(){root=cnt=last[1]=1; return ;}int Insert(int f,int p){int v=++cnt; mx[v]=mx[p]+1;Lct::tree[v].size=1;while(p&&s[p][f]==0) s[p][f]=v,p=fail[p];if(p==0) {fail[v]=root; ans+=mx[v]-mx[fail[v]]; Lct::Link(v,1); return v;}int q=s[p][f];if(mx[p]+1==mx[q]) {fail[v]=q; ans+=mx[v]-mx[fail[v]]; Lct::Link(v,q); return v;}int o=++cnt; mx[o]=mx[p]+1;memcpy(s[o],s[q],12);fail[o]=fail[q]; Lct::Link(o,fail[q]);fail[q]=fail[v]=o;Lct::Cut(q); Lct::Link(q,o); Lct::Link(v,o);while(p&&s[p][f]==q) s[p][f]=o,p=fail[p];ans+=mx[v]-mx[fail[v]];return v;}inline int Ask(){scanf("%s",ssr);int len=strlen(ssr),v=root;for(int i=0;i<len;i++)if((v=s[v][ssr[i]-'a'])==0) return 0;Lct::Splay(v); return Lct::tree[v].size;}
}
struct Branch {int next,to,val;} branch[Maxn<<1];
int h[Maxn],cnt=0;
inline void add(int x,int y,int z){branch[++cnt].to=y; branch[cnt].next=h[x]; h[x]=cnt; branch[cnt].val=z; return ;
}
int vis[Maxn];
void Dfs(int v){vis[v]=1;for(int i=h[v];i;i=branch[i].next){int j=branch[i].to;if(vis[j]) continue;Sam::last[j]=Sam::Insert(branch[i].val,Sam::last[v]);Dfs(j);} return ;
}
int main(){read();n=read();for(int i=1;i<n;i++){int x=read(),y=read(),z=cread();add(x,y,z); add(y,x,z);}Sam::Reset(); Dfs(1);m=read();for(int i=1;i<=m;i++){int f=read();if(f==1) cout<<ans<<'\n';else if(f==2){int v=read(),k=read();for(int j=1;j<k;j++){int x=read(),y=read(),z=cread();add(x,y,z); add(y,x,z);}Dfs(v);}else cout<<Sam::Ask()<<'\n';}return 0;
}PART 4
子树维护
点修改维护子树
链修改维护子树
静态树结构下的子树修改维护子树
子树与链修改(toptree)
LCT是一个好东西，但是Tarjan并没有让它维护子树的打算。
我们的lct维护的都是链上的信息，这是因为Splay对应的都是对于原树的路径剖分。
那么我们怎样来维护子树信息呢？向您强力推荐%%%neither_nor%%%
简单来说，就是在Access改变路径剖分时记录边的虚实关系，LCT子树信息就是实子树和虚子树的合并(当然要包含当前节点啦)
看一下这个最经典的题目：
【BJOI2014】大融合
Description
小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。 
例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。
现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。
Input
第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。
接下来的Q行，每行是如下两种格式之一：
A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。
Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。
Output
对每个查询操作，输出被查询的边的负载。
Sample Input
8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8
Sample Output
6
Hint
对于40%的数据，N,Q≤1000
对于100%的数据，1≤N,Q≤100000
我们发现，这个时候维护答案就是两个节点对应的子树大小(以对方为根)
那么怎么维护子树大小？
将一个节点对应的lct子树的size分为三个部分：实子树的size大小，当前节点的虚子树大小以及当前节点(size=1)
有趣的地方有这三个：
inline void Pushup(int v){
tree[v].size=tree[tree[v].s[0]].size+tree[tree[v].s[1]].size+tree[v].vsize+1;
return ;
}
inline void Access(int v){
for(int u=0;v;u=v,v=tree[v].F){
Splay(v); tree[v].vsize+=tree[tree[v].s[1]].size;
tree[v].s[1]=u; tree[v].vsize-=tree[u].size; Pushup(v);
} return ;
}
inline void Link(int v,int u){
Make_Root(v); Make_Root(u);
tree[v].F=u; tree[u].vsize+=tree[v].size; Pushup(u);
return ;
}
简单来讲就是每一次将一条虚实边的切换时维护当前节点的vsize(virtual size)大小即可
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=100005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
struct Splay{int F,s[2],rev;int size,vsize;
}tree[Maxn];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void Pushup(int v){tree[v].size=tree[tree[v].s[0]].size+tree[tree[v].s[1]].size+tree[v].vsize+1; return ;}
inline void Rev(int v){tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}
inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}
void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}
inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}
inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(Isroot(p))tree[v].F=g; else Set(g,v,t2); Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;
}
inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;
}
inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F){Splay(v); tree[v].vsize+=tree[tree[v].s[1]].size;tree[v].s[1]=u; tree[v].vsize-=tree[u].size; Pushup(v);} return ;
}
inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}
inline void Split(int v,int u){Make_Root(v); Access(u); Splay(u); return ;}
inline void Link(int v,int u){Make_Root(v); Make_Root(u); tree[v].F=u; tree[u].vsize+=tree[v].size; Pushup(u); return ;}
int main(){int n=read(),m=read(); char ch;for(int i=1;i<=m;i++){while((ch=getchar())!='A'&&ch!='Q');int x=read(),y=read();if(ch=='A') Link(x,y);else {Split(x,y); cout<<(long long)(tree[x].vsize+1)*(tree[y].vsize+1)<<'\n';}}return 0;
}//可以说是非常经典的入门题目了那么我们开始维护一些更高级的东西了233
【BZOJ3306】树
Description
给定一棵大小为 n 的有根点权树,支持以下操作:
• 换根
• 修改点权
• 查询子树最小值
Input
第一行两个整数 n, Q ,分别表示树的大小和操作数。
接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f < i。如 果f = 0,那么i为根。输入数据保证只有i = 1时,f = 0。
接下来 m 行,为以下格式中的一种:
• V x y表示把点x的权改为y
• E x 表示把有根树的根改为点 x
• Q x 表示查询点 x 的子树最小值
Output
对于每个 Q ,输出子树最小值。
Sample Input
3 7
0 1
1 2
1 3
Q 1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1
Sample Output
1
2
3
4
Hint
对于 100% 的数据:n, Q ≤ 10^5。
单点修改，子树最小值本来是可以用简单的树链剖分高效维护的，但是换根的操作确实有点恶心。我们当然可以用讨论的方式来解决真正的子树区间，但是讨论的过程确实不太优美。所以我们干脆用lct来维护这个东西。
子树的最小值就是实子树的最小值和虚子树的最小值的较小值(干脆把当前节点的值归入实子树当中)。
我们可以对每一个节点开一个multiset来维护。
如何方便快捷的完成单点修改呢？我们把当前节点通过Access和Splay的方式移动到没有虚父亲也没有实父亲的地方，然后直接修改和维护当前节点的最小值即可。
时间复杂度O（nlog^2n）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
const int Maxn=100005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m;
struct Splay{int F,s[2],rev;int val,mn;multiset<int> S;inline void NewNode(int fa,int x){F=fa; s[0]=s[1]=rev=0;val=mn=x; S.insert(x); return ;}inline void Erase(int x){S.erase(S.find(x)); return ;}
}tree[Maxn];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void Pushup(int v){tree[v].mn=min(min(tree[tree[v].s[0]].mn,tree[tree[v].s[1]].mn),*(tree[v].S.begin()));return ;}
inline void Rev(int v){tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}
inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}
void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}
inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}
inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(Isroot(p))tree[v].F=g; else Set(g,v,t2); Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;
}
inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;
}
inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F){Splay(v);if(u) tree[v].S.erase(tree[v].S.find(tree[u].mn));if(tree[v].s[1]) tree[v].S.insert(tree[tree[v].s[1]].mn);tree[v].s[1]=u; Pushup(v);} return ;
}
inline void Split(int v){Access(v); Splay(v); return ;}
int main(){n=read(); m=read(); char ch;tree[0].NewNode(0,0x3f3f3f3f);for(int i=1;i<=n;i++){int x=read(),y=read();tree[i].NewNode(x,y);}for(int i=n;i;--i) Pushup(i),tree[tree[i].F].S.insert(tree[i].mn);for(int i=1;i<=m;i++){while((ch=getchar())!='V'&&ch!='E'&&ch!='Q');int x=read();if(ch=='V'){Split(x); tree[x].Erase(tree[x].val);tree[x].val=read(); tree[x].S.insert(tree[x].val);Pushup(x);}else if(ch=='E') Split(x),Rev(x);else Split(x),cout<<*(tree[x].S.begin())<<'\n';//这里的Set包含了当前节点的权值}return 0;
}单点修改太过于简单，不符合我们的树巨结垢的审美观念。
【BZOJ3083】遥远的国度
Description
zcwwzdjn在追杀十分sb的zhx，而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时，守护神RapiD阻拦了zcwwzdjn的去路，他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。
问题是这样的：遥远的国度有n个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题，所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx，所以这个重大的问题就被转交到了你的手上。
Input
第1行两个整数n m，代表城市个数和操作数。
第2行至第n行，每行两个整数 u v，代表城市u和城市v之间有一条路。
第n+1行，有n个整数，代表所有点的初始防御值。
第n+2行一个整数 id，代表初始的首都为id。
第n+3行至第n+m+2行，首先有一个整数opt，如果opt=1，接下来有一个整数id，代表把首都修改为id；如果opt=2，接下来有三个整数p1 p2 v，代表将p1 p2路径上的所有城市的防御值修改为v；如果opt=3，接下来有一个整数 id，代表询问以城市id为根的子树中的最小防御值。
Output
对于每个opt=3的操作，输出一行代表对应子树的最小点权值。
Sample Input
3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1
Sample Output
1
2
3
4
Hint
【数据范围】
对于20%的数据，n<=1000 m<=1000。
对于另外10%的数据，n<=100000，m<=100000，保证修改为单点修改。
对于另外10%的数据，n<=100000，m<=100000，保证树为一条链。
对于另外10%的数据，n<=100000，m<=100000，没有修改首都的操作。
对于100%的数据，n<=100000，m<=100000，0<所有权值<=2^31。
我们这个时候就要把信息分为两类：chain和subtree
我们的chain(简称cha)只包括实链上的信息，而subtree(简称sub)包含了所有实链节点上面挂着的虚子树信息。
我们的标记只和cha有关，sub信息的更改只在当前节点和access时发生改变。
一定要注意cha和sub的分离，否则的话一团乱麻，根本不能维护。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
const int Maxn=100005;
const int Inf=1<<30;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m;
struct Splay{int F,s[2],val;int minn,ms,mc;int rev,cov;multiset<int> S;inline void NewNode(int fa,int x){F=fa; s[0]=s[1]=rev=0;val=minn=mc=x; ms=Inf; S.insert(Inf);rev=cov=0; return ;}inline void Erase(int x){S.erase(S.find(x)); return ;}
}tree[Maxn];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void Pushup(int v){tree[v].mc=min(tree[v].val,min(tree[tree[v].s[0]].mc,tree[tree[v].s[1]].mc));tree[v].ms=min(*(tree[v].S.begin()),min(tree[tree[v].s[0]].ms,tree[tree[v].s[1]].ms));tree[v].minn=min(tree[v].mc,tree[v].ms); return ;
}
inline void Rev(int v){if(v==0) return ; tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}
inline void Cov(int v,int x){if(v==0) return ; tree[v].cov=x; tree[v].val=x; tree[v].mc=x;tree[v].minn=min(tree[v].mc,tree[v].ms); return ;
}
inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;}if(tree[v].cov){Cov(tree[v].s[0],tree[v].cov); Cov(tree[v].s[1],tree[v].cov); tree[v].cov=0;}return ;
}
inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}
inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}
inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(Isroot(p)) tree[v].F=g; else Set(g,v,t2);Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;
}
inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;
}
inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F){Splay(v);if(u) tree[v].Erase(tree[u].minn);if(tree[v].s[1]) tree[v].S.insert(tree[tree[v].s[1]].minn);tree[v].s[1]=u; Pushup(v);} return ;
}
inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}
inline void Change(int v,int u,int x){Make_Root(v); Access(u); Splay(u); Cov(u,x); return ;}
inline void Get_Path(int v){Access(v); Splay(v); return ;}
int root,val[Maxn];
struct Branch {int next,to;} branch[Maxn<<1];
int h[Maxn],cnt=0;
inline void add(int x,int y){branch[++cnt].to=y; branch[cnt].next=h[x]; h[x]=cnt; return ;
}
void Dfs(int v,int pre){tree[v].NewNode(pre,val[v]);for(int i=h[v];i;i=branch[i].next){int j=branch[i].to;if(j==pre) continue;Dfs(j,v);}Pushup(v);tree[pre].S.insert(tree[v].minn);return ;
}
int main(){n=read(); m=read();for(int i=1;i<n;i++){int x=read(),y=read();add(x,y); add(y,x);}for(int i=1;i<=n;i++) val[i]=read();tree[0].NewNode(0,1<<30);root=read(); Dfs(root,0); Make_Root(root);for(int i=1;i<=m;i++){int f=read(),x=read();if(f==1){root=x; Make_Root(x);}else if(f==2){int y=read(),z=read();Change(x,y,z); Make_Root(root);}else {Get_Path(x);int minn=min(tree[x].val,*(tree[x].S.begin()));cout<<minn<<'\n';}}return 0;
}就像之前目录提到的，接下来是静态树结构维护子树修改信息。
【SDOI2017】树点涂色
Description
Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：
1 x:
把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:
求x到y的路径的权值。
3 x:
在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。
Bob一共会进行m次操作
Input
第一行两个数n,m。
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。
接下来m行，表示操作，格式见题目描述
1<=n,m<=100000
Output
每当出现2,3操作，输出一行。
如果是2操作，输出一个数表示路径的权值
如果是3操作，输出一个数表示权值的最大值
Sample Input
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
Sample Output
3
4
2
2
emm，这玩意和LCT有什么关系呢？
询问似乎是可以树链剖分来完成的，但是修改操作。。。（思考一下）
是不是很像LCT的Access操作？
显然吧。
在Access的过程中，每一次虚实边的转换，就会使得对应的子树答案加减1。
也就是说，因为LCT不是很好维护子树修改，所以我们用LCT来维护修改操作用的位置信息，然后使用线段树维护。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=100005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m;
namespace Graph{struct Branch {int next,to;} branch[Maxn<<1];int h[Maxn],cnt=0;inline void add(int x,int y){branch[++cnt].to=y; branch[cnt].next=h[x]; h[x]=cnt; return ;}int size[Maxn],deep[Maxn];int top[Maxn],fa[Maxn],son[Maxn];int id[Maxn],pos[Maxn],low[Maxn],ind=0;void Dfs1(int v,int pre,int dep){size[v]=1; fa[v]=pre; deep[v]=dep;for(int i=h[v];i;i=branch[i].next){int j=branch[i].to;if(j==pre) continue;Dfs1(j,v,dep+1); size[v]+=size[j];if(size[son[v]]<size[j]) son[v]=j;} return ;}void Dfs2(int v,int T){id[v]=++ind; pos[ind]=v; top[v]=T;if(son[v]) Dfs2(son[v],T);for(int i=h[v];i;i=branch[i].next){int j=branch[i].to;if(j==fa[v]||j==son[v]) continue;Dfs2(j,j);}low[v]=ind; return ;}inline int Lca(int x,int y){while(top[x]!=top[y])deep[top[x]]<deep[top[y]]?y=fa[top[y]]:x=fa[top[x]];return deep[x]<deep[y]?x:y;}
}
namespace SGT{struct Segment_Tree{int L,R,maxx,add;}tree[Maxn<<2];inline void Pushup(int v){tree[v].maxx=max(tree[v<<1].maxx,tree[v<<1|1].maxx); return ;}inline void Add(int v,int x){if(v) tree[v].add+=x,tree[v].maxx+=x; return ;}inline void Pushdown(int v){if(tree[v].add){Add(v<<1,tree[v].add);Add(v<<1|1,tree[v].add);tree[v].add=0;}return ;}void Build(int v,int L,int R){tree[v].L=L; tree[v].R=R; tree[v].add=0;if(L==R){tree[v].maxx=Graph::deep[Graph::pos[L]]; return ;}int mid=(L+R)>>1;Build(v<<1,L,mid); Build(v<<1|1,mid+1,R);Pushup(v); return ;}void Mod(int v,int L,int R,int x){if(tree[v].L>R||tree[v].R<L) return ;if(L<=tree[v].L&&tree[v].R<=R){Add(v,x); return ;}Pushdown(v);Mod(v<<1,L,R,x); Mod(v<<1|1,L,R,x);Pushup(v); return ;}int Ask(int v,int L,int R){if(tree[v].L>R||tree[v].R<L) return 0;if(L<=tree[v].L&&tree[v].R<=R) return tree[v].maxx;Pushdown(v);return max(Ask(v<<1,L,R),Ask(v<<1|1,L,R));}
}
namespace Lct{struct Splay{int F,s[2],rev;}tree[Maxn];inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}inline void Rev(int v){if(v) tree[v].rev^=1,swap(tree[v].s[0],tree[v].s[1]); return ;}inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; tree[v].F=g;Set(v,p,!t1); Set(p,S,t1); return ;}inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} return ;}inline int Top(int v){while(tree[v].s[0]) Pushdown(v),v=tree[v].s[0]; return v;}inline void Access(int v){for(int u=0,pos;v;u=v,v=tree[v].F){Splay(v); pos=Top(tree[v].s[1]);if(pos) SGT::Mod(1,Graph::id[pos],Graph::low[pos],1);tree[v].s[1]=u; pos=Top(u);if(pos) SGT::Mod(1,Graph::id[pos],Graph::low[pos],-1);} return ;}inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}inline void Reset(){for(int i=1;i<=n;i++) tree[i].F=Graph::fa[i]; return ;}
}
int main(){n=read(); m=read();for(int i=1;i<n;i++){int x=read(),y=read();Graph::add(x,y); Graph::add(y,x);}Graph::Dfs1(1,0,1); Graph::Dfs2(1,1);SGT::Build(1,1,n); Lct::Reset();for(int i=1;i<=m;i++){int f=read();if(f==1) Lct::Access(read());else if(f==2){int x=read(),y=read(),p=Graph::Lca(x,y),ans=1;ans+=SGT::Ask(1,Graph::id[x],Graph::id[x]);ans+=SGT::Ask(1,Graph::id[y],Graph::id[y]);ans-=SGT::Ask(1,Graph::id[p],Graph::id[p])<<1;cout<<ans<<'\n';}else {int x=read();cout<<SGT::Ask(1,Graph::id[x],Graph::low[x])<<'\n';}}return 0;
}Part 5
其他的一些题目
【BZOJ3510】首都
Description
在X星球上有N个国家，每个国家占据着X星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。
X星球上战乱频发，如果A国打败了B国，那么B国将永远从这个星球消失，而B国的国土也将归A国管辖。A国国王为了加强统治，会在A国和B国之间修建一条公路，即选择原A国的某个城市和B国某个城市，修建一条连接这两座城市的公路。
同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。
现在告诉你发生在X星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下3种信息需要处理：
1、A x y：表示某两个国家发生战乱，战胜国选择了x城市和y城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
2、Q x：询问当前编号为x的城市所在国家的首都。
3、Xor：询问当前所有国家首都编号的异或和。
Input
第一行是整数N，M，表示城市数和需要处理的信息数。
接下来每行是一个信息，格式如题目描述（A、Q、Xor中的某一种）。
Output
输出包含若干行，为处理Q和Xor信息的结果。
Sample Input
10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor
Sample Output
11
1
1
1
2
6
2
题目相信大家如果前面的题目都看过了那么应该看得懂。
那么问题来了，如何动态维护当前联通块的重心呢？
网上常见的解法是使用启发式合并，每次将小块的点一个一个加入到大联通块中。
时间复杂度O(nlog^2n)
这种写法感觉不是很优美，没有用到重心的性质。
那么什么是重心的性质呢？
两棵树连边之后，新的重心在原有两个重心的连线上。
所以我们就可以二分答案了。
这样的时间复杂度是O(nlogn)的.
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=100005;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m,ans;
int fa[Maxn];
inline int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
struct Splay{int F,s[2],rev,size,vsize;
}tree[Maxn];
inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
inline void Pushup(int v){tree[v].size=tree[tree[v].s[0]].size+tree[tree[v].s[1]].size+tree[v].vsize+1; return ;}
inline void Rev(int v){if(v==0) return ; tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}
inline void Pushdown(int v){if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}
inline void Lazy(int v){if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}
inline void Set(int v,int u,int f){tree[v].s[f]=u; tree[u].F=v; return ;}
inline void Rotate(int v){int p=tree[v].F,g=tree[p].F;int t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(Isroot(p)) tree[v].F=g; else Set(g,v,t2);Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;
}
inline void Splay(int v){for(Lazy(v);!Isroot(v);Rotate(v)){int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;
}
inline void Access(int v){for(int u=0;v;u=v,v=tree[v].F){Splay(v);tree[v].vsize-=tree[u].size;tree[v].vsize+=tree[tree[v].s[1]].size;tree[v].s[1]=u; Pushup(v);} return ;
}
inline void Make_Root(int v){Access(v); Splay(v); Rev(v); return ;}
inline void Split(int v,int u){Make_Root(v); Access(u); Splay(u); return ;}
inline void Link(int v,int u){Make_Root(v); Make_Root(u);tree[v].F=u; tree[u].vsize+=tree[v].size; Pushup(u);return ;
}
inline void Sov(int v,int u){Split(v,u);int x=u,tot=tree[u].size,even=tot&1,pos=0x3f3f3f3f;int lsum=0,rsum=0,L,R;while(x){Pushdown(x);L=tree[tree[x].s[0]].size+lsum;R=tree[tree[x].s[1]].size+rsum;if(L<=(tot>>1)&&R<=(tot>>1)){if(even){pos=x; break;}else pos=pos<x?pos:x;}if(L<R) lsum+=tree[tree[x].s[0]].size+tree[x].vsize+1,x=tree[x].s[1];else rsum+=tree[tree[x].s[1]].size+tree[x].vsize+1,x=tree[x].s[0];}Splay(pos); ans=ans^v^u^pos;fa[u]=fa[v]=fa[pos]=pos;return ;
}
int main(){n=read(); m=read(); char ch;for(int i=1;i<=n;i++) ans=ans^i,fa[i]=i,tree[i].size=1;for(int i=1;i<=m;i++){while((ch=getchar())!='A'&&ch!='Q'&&ch!='X');if(ch=='A'){int x=read(),y=read();Link(x,y);x=getfa(x); y=getfa(y);Sov(x,y);}else if(ch=='Q') cout<<getfa(read())<<'\n';else cout<<ans<<'\n';}return 0;
}这样写在洛谷上跑得还行(BZOJ买不起233)
接下来是一个很神奇的题目。
【BZOJ3159】决战
Description
Input
第一行有三个整数N、M和R，分别表示树的节点数、指令和询问总数，以及X国的据点。
接下来N-1行，每行两个整数X和Y，表示Katharon国的一条道路。
接下来M行，每行描述一个指令或询问，格式见题目描述。
Output
对于每个询问操作，输出所求的值。
Sample Input
5 8 1
1 2
2 3
3 4
4 5
Sum 2 4
Increase 3 5 3
Minor 1 4
Sum 4 5
Invert 1 3
Major 1 2
Increase 1 5 2
Sum 1 5
Sample Output
0
0
6
3
19
Hint
1<=N,M<=50000.且对于运送操作1<=W<=1000
除去第五个权值翻转操作，其余的部分都是可以使用LCT甚至树链剖分完成的模板题。
那么怎么完成权值的翻转呢？
我们似乎记得LCT中也有链翻转的操作，可不可以直接用到这道题上？
答案是否定的(要不然这道题就会出现在前面)
因为LCT中Splay的中序遍历维护的是原树上链的深度序，如果我们将一条链翻转，那么树的形态结构就会发生变化。
我们知道，简单的Splay是支持翻转的。
那么，我们就可以在维护结构的LCT的同时，维护LCT中节点对应的权值Splay。
或者说，我们用LCT维护了一个节点到权值的映射，我们如果能够做到LCT上的每一个Spaly都对应着一颗相同的权值Spaly的话，我们就可以直接在权值Splay上打rev标记来解决链上权值翻转的问题了。
具体怎么做呢？
我们在LCT中的每一个节点维护对应的Splay的根（是的，对应根）。
然后我们要查找对应节点x的权值时，我们可以得出当前节点在Splay中的深度排序k。对应的，Splay树中的第k个节点记录的就是x的权值。
根据我们之前维护子树信息时了解到的知识，只有在Access的时候才会改变树剖分的结构，我们Splay的分裂与合并就是在这个时候直接维护的。
——————————————————————我是法二的分割线———————————————————————
我们知道这棵树的形态没有发生过变化。也就是说静态的树链剖分是可以解决问题的。
那么怎样做到链翻转呢？
注意：我们常见的树链剖分使用线段树维护询问。
但事实上，任意能够维护区间信息的数据结构都可以维护树剖的信息，包括Splay。
也就是说说，我们直接用Splay维护每一条重链。
询问和正常的树剖一样。
翻转时，我们把logn段Splay提取出来，按照顺序拼在一起，打上rev标记之后再重新拆开塞回去。
是不是特别简单易懂？(就是难写难调)
/*
两棵lct维护法（事实上我觉得权值部分跟像是一个平衡树森林，能够维护序列的平衡树都可以）
Val部分维护权值，Form部分维护结构
命名空间套结构体套结构体显得不好看（但是好调啊233）
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=50005;
typedef long long ll;
inline int read() {static char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int n,m,ROOT;
struct Val_Node {int F,s[2],size;ll val,sum,maxx,minn;int add,rev;inline void NewNode(int fa,ll x) {F=fa; s[0]=s[1]=0; size=1; add=rev=0;val=sum=maxx=minn=x; return ;}
};
struct Vt {Val_Node tree[Maxn];Vt(){tree[0].minn=0x3f3f3f3f; tree[0].maxx=-0x3f3f3f3f;}inline bool Isroot(int v) {return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}inline void Pushup(int v) {tree[v].size=tree[tree[v].s[0]].size+1+tree[tree[v].s[1]].size;tree[v].sum=tree[tree[v].s[0]].sum+tree[v].val+tree[tree[v].s[1]].sum;tree[v].minn=min(tree[v].val,min(tree[tree[v].s[0]].minn,tree[tree[v].s[1]].minn));tree[v].maxx=max(tree[v].val,max(tree[tree[v].s[0]].maxx,tree[tree[v].s[1]].maxx));return ;}inline void Rev(int v) {if(v==0) return ; tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}inline void Add(int v,ll x) {if(v==0) return ;tree[v].add+=x; tree[v].val+=x;tree[v].minn+=x; tree[v].maxx+=x;tree[v].sum+=tree[v].size*x; return ;}inline void Pushdown(int v) {if(tree[v].rev) {Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;}if(tree[v].add) { Add(tree[v].s[0],tree[v].add); Add(tree[v].s[1],tree[v].add); tree[v].add=0;} return ;}inline void Lazy(int v) {if(!Isroot(v)) Lazy(tree[v].F); Pushdown(v); return ;}inline void Set(int v,int u,int f) {tree[v].s[f]=u; if(u) tree[u].F=v; return ;}inline void Rotate(int v) {int p=tree[v].F,g=tree[p].F,t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; if(v)tree[v].F=g; Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;}inline void Splay(int v) {for(Lazy(v);!Isroot(v);Rotate(v)) {int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;}inline int Get_Root(int &v) {while(tree[v].F&&tree[v].F!=v) v=tree[v].F; return v;}inline void Kth(int &v,int k) {while(1) {Pushdown(v);if(tree[tree[v].s[0]].size+1==k) return ;if(k<=tree[tree[v].s[0]].size) v=tree[v].s[0];else k-=tree[tree[v].s[0]].size+1,v=tree[v].s[1];} return ;}
};
struct Form_Node {int F,s[2],rt;int size,rev;inline void NewNode(int fa,int x) {F=fa; s[0]=s[1]=rev=0;rt=x; size=1; return ;}
};
struct Ft {Form_Node tree[Maxn];inline bool Isroot(int v) {return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}inline void Pushup(int v) {tree[v].size=tree[tree[v].s[0]].size+1+tree[tree[v].s[1]].size; return ;}inline void Rev(int v) {tree[v].rev^=1; swap(tree[v].s[0],tree[v].s[1]); return ;}inline void Pushdown(int v) {if(tree[v].rev){Rev(tree[v].s[0]); Rev(tree[v].s[1]); tree[v].rev=0;} return ;}inline int Lazy(int v) {int rec=Isroot(v)?v:Lazy(tree[v].F); Pushdown(v); return rec;}inline void Set(int v,int u,int f) {tree[v].s[f]=u; tree[u].F=v; return ;}inline void Rotate(int v) {int p=tree[v].F,g=tree[p].F,t1=(v==tree[p].s[1]),t2=(p==tree[g].s[1]),S=tree[v].s[!t1];if(!Isroot(p)) tree[g].s[t2]=v; tree[v].F=g; Set(v,p,!t1); Set(p,S,t1); Pushup(p); return ;}inline void Splay(int v) {for(tree[v].rt=tree[Lazy(v)].rt;!Isroot(v);Rotate(v)) {int p=tree[v].F,g=tree[p].F;if(!Isroot(p)) Rotate((v==tree[p].s[1])^(p==tree[g].s[1])?v:p);} Pushup(v); return ;}
};
namespace Lct {Vt Value; Ft Form;inline void Access(int v) {for(int u=0;v;u=v,v=Form.tree[v].F) {Form.Splay(v);int x=Value.Get_Root(Form.tree[v].rt),y=Value.Get_Root(Form.tree[u].rt);Value.Kth(x,Form.tree[Form.tree[v].s[0]].size+1);Value.Splay(x); Form.tree[v].rt=x;Form.tree[Form.tree[v].s[1]].rt=Value.tree[x].s[1];Value.tree[Value.tree[x].s[1]].F=0;Value.tree[x].s[1]=y; if(y) Value.tree[y].F=x; Value.Pushup(x);Form.tree[v].s[1]=u; Form.Pushup(v);} return ;}inline void Make_Root(int v) {Access(v); Form.Splay(v); Form.Rev(v); Value.Rev(Form.tree[v].rt); return ;}inline void Split(int v,int u) {Make_Root(v); Access(u); Form.Splay(u); return ;}
}
struct Branch {int next,to;} branch[Maxn<<1];
int h[Maxn],cnt=0;
inline void add(int x,int y) {branch[++cnt].to=y; branch[cnt].next=h[x]; h[x]=cnt; return ;
}
inline void Dfs(int v,int pre) {Lct::Form.tree[v].NewNode(pre,v);Lct::Value.tree[v].NewNode(0,0);for(int i=h[v];i;i=branch[i].next) {int j=branch[i].to;if(j==pre) continue;Dfs(j,v);} return ;
}
int main() {n=read(); m=read(); ROOT=read();for(int i=1;i<n;++i) {int x=read(),y=read();add(x,y); add(y,x);}Dfs(ROOT,0); char ch;for(int i=1;i<=m;++i) {while((ch=getchar())!='S'&&ch!='c'&&ch!='j'&&ch!='i'&&ch!='v');int x=read(),y=read();Lct::Split(x,y); int rt=Lct::Value.Get_Root(Lct::Form.tree[y].rt);switch(ch) {case 'c' : Lct::Value.Add(rt,read()); break;case 'S' : cout<<Lct::Value.tree[rt].sum<<'\n'; break;case 'j' : cout<<Lct::Value.tree[rt].maxx<<'\n'; break;case 'i' : cout<<Lct::Value.tree[rt].minn<<'\n'; break;case 'v' : Lct::Value.Rev(rt); break;}}return 0;
}/*
法二
锻炼码力的好方法
看看那个奇丑无比的Inversal函数
有兴趣的话可以试试~
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=100005;
const int Inf=0x3f3f3f3f;
inline int read(){char c; int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9') rec=rec*10+c-'0',c=getchar();return rec;
}
int cnt,sz,n,m,k,top[Maxn],deep[Maxn],son[Maxn],f[Maxn];
int ch[Maxn][3],root,rt,a[Maxn],id[Maxn],fa[Maxn],rev[Maxn];
long long mx[Maxn],mn[Maxn],sum[Maxn],val[Maxn],tag[Maxn],size[Maxn];
struct data{int x,l,r;
}c[Maxn];
char s[20];
struct Branch {int next,to;} branch[Maxn<<1];
int h[Maxn],tot;
inline void add(int x,int y){branch[++tot].to=y; branch[tot].next=h[x]; h[x]=tot; return ;
}
void Dfs1(int v,int pre,int dep){size[v]=1; f[v]=pre; deep[v]=dep;for(int i=h[v];i;i=branch[i].next){int j=branch[i].to;if(j==pre) continue;Dfs1(j,v,dep+1); size[v]+=size[j];if(size[son[v]]<size[j]) son[v]=j;} return ;
}
void Dfs2(int v,int T){id[v]=++sz; a[sz]=v; ::top[v]=T;if(son[v]) Dfs2(son[v],T);for(int i=h[v];i;i=branch[i].next){int j=branch[i].to;if(j==f[v]||j==son[v]) continue;Dfs2(j,j);} return ;
}
inline void change(int now,long long delta){val[now]+=delta; mn[now]+=delta; mx[now]+=delta;sum[now]+=size[now]*delta; tag[now]+=delta;
}
inline void Pushdown(int now){if(tag[now]){change(ch[now][0],tag[now]);change(ch[now][1],tag[now]);tag[now]=0;}if(rev[now]){swap(ch[now][1],ch[now][0]);rev[ch[now][0]]^=1; rev[ch[now][1]]^=1; rev[now]=0;} return ;
}
inline void Pushup(int now){int l=ch[now][0]; int r=ch[now][1]; tag[now]=0;sum[now]=mx[now]=mn[now]=val[now]; size[now]=1;if(l) sum[now]+=sum[l],size[now]+=size[l],mx[now]=max(mx[now],mx[l]),mn[now]=min(mn[now],mn[l]);if(r) sum[now]+=sum[r],size[now]+=size[r],mx[now]=max(mx[now],mx[r]),mn[now]=min(mn[now],mn[r]);
}
void Lazy(int v){if(fa[v]) Lazy(fa[v]); Pushdown(v); return ;}
inline void Rotate(int v){int p=fa[v],g=fa[p];int t1=(v==ch[p][1]),t2=(p==ch[g][1]),S=ch[v][!t1];if(g) ch[g][t2]=v; fa[v]=g;ch[v][!t1]=p; fa[p]=v;ch[p][t1]=S; fa[S]=p;Pushup(p); return ;
}
inline void Splay(int v,int tar,int &RT){for(Lazy(v);fa[v]!=tar;Rotate(v)){int p=fa[v],g=fa[p];if(g!=tar) Rotate((v==ch[p][1])^(p==ch[g][1])?v:p);} Pushup(v); if(tar==0) RT=v;
}
int find(int now,int x){while (1) {Pushdown(now);if(size[ch[now][0]]>=x) now=ch[now][0];else {x-=size[ch[now][0]];if(x==1) return now;x--; now=ch[now][1];}}
}
int build(int l,int r){if(l>r) return 0;if(l==r){size[++cnt]=1; return cnt;}int mid=(l+r)/2; int now=++cnt; ch[now][0]=build(l,mid-1); fa[ch[now][0]]=now;ch[now][1]=build(mid+1,r); fa[ch[now][1]]=now;Pushup(now); return now;
}
void init(){rt=++cnt; int now=++cnt;ch[rt][1]=now; fa[now]=rt; size[now]=1;size[rt]=2; return ;
}
inline int Prepare(int x,int y){int aa=find(root,x-1); int bb=find(root,y+1);Splay(aa,0,root); Splay(bb,aa,root);return ch[ch[root][1]][0];
}
inline void Sov(int x,int y,int z){while (top[x]!=top[y]){if(deep[top[x]]<deep[top[y]]) swap(x,y);int t=Prepare(id[top[x]],id[x]);change(t,z);x=f[top[x]];}if(deep[x]>deep[y]) swap(x,y);int t=Prepare(id[x],id[y]);change(t,z);
}
inline long long Sum(int x,int y){long long rec=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]]) swap(x,y);rec+=sum[Prepare(id[top[x]],id[x])];x=f[top[x]];} if(deep[x]>deep[y]) swap(x,y);rec+=sum[Prepare(id[x],id[y])];return rec;
}
inline long long Maxx(int x,int y){long long rec=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]]) swap(x,y);rec=max(rec,mx[Prepare(id[top[x]],id[x])]);x=f[top[x]];} if(deep[x]>deep[y]) swap(x,y);rec=max(rec,mx[Prepare(id[x],id[y])]);return rec;
}
inline long long Minn(int x,int y){long long rec=Inf;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]]) swap(x,y);rec=min(rec,mn[Prepare(id[top[x]],id[x])]);x=f[top[x]];} if(deep[x]>deep[y]) swap(x,y);rec=min(rec,mn[Prepare(id[x],id[y])]);return rec;
}
void Inversal(int x,int y){int top=1; tot=0; Pushdown(rt);while(::top[x]!=::top[y]){if(deep[::top[x]]<deep[::top[y]]) swap(x,y);int t=Prepare(id[::top[x]],id[x]); ch[ch[root][1]][0]=0;fa[t]=0; Pushup(ch[root][1]); Pushup(root);++tot; c[tot].x=id[::top[x]]-1;int len=id[x]-id[::top[x]]+1;c[tot].l=top+1; c[tot].r=top+len;int aa=find(rt,top); int bb=find(rt,top+1);Splay(aa,0,rt); Splay(bb,aa,rt);ch[ch[rt][1]][0]=t; fa[t]=ch[rt][1]; rev[t]^=1;Pushup(ch[rt][1]); Pushup(rt);top=c[tot].r;x=f[::top[x]];}if(deep[x]>deep[y]) swap(x,y);int t=Prepare(id[x],id[y]);ch[ch[root][1]][0]=0;fa[t]=0; Pushup(ch[root][1]); Pushup(root);++tot; c[tot].x=id[x]-1;int len=id[y]-id[x]+1;c[tot].l=top+1; c[tot].r=top+len;int aa=find(rt,top); int bb=find(rt,top+1);Splay(aa,0,rt); Splay(bb,aa,rt);ch[ch[rt][1]][0]=t; fa[t]=ch[rt][1]; rev[t]^=1;Pushup(ch[rt][1]); Pushup(rt);top=c[tot].r;rev[rt]^=1;for(int i=tot;i>=1;i--){int aa=find(rt,c[i].l-1); int bb=find(rt,c[i].r+1);Splay(aa,0,rt); Splay(bb,aa,rt);int t=ch[ch[rt][1]][0];ch[ch[rt][1]][0]=0; fa[t]=0; Pushup(ch[rt][1]); Pushup(rt);aa=find(root,c[i].x); bb=find(root,c[i].x+1);Splay(aa,0,root); Splay(bb,aa,root);ch[ch[root][1]][0]=t; fa[t]=ch[root][1]; rev[t]^=1;Pushup(ch[root][1]); Pushup(root);} return ;
}
int main(){n=read(); m=read(); k=read();for(int i=1;i<n;i++){int x=read(),y=read();add(x,y); add(y,x);}Dfs1(k,0,1); memset(size,0,sizeof(size));sz=1; Dfs2(k,k);root=build(1,n+2); init();for(int i=1;i<=m;i++){int x,y,z; scanf("%s",s+1);x=read(); y=read();if(s[1]=='I'&&s[3]=='c') Sov(x,y,read());if(s[1]=='S') cout<<Sum(x,y)<<'\n';if(s[1]=='M'&&s[2]=='a') cout<<Maxx(x,y)<<'\n';if(s[1]=='M'&&s[2]=='i') cout<<Minn(x,y)<<'\n';if(s[1]=='I'&&s[3]=='v') Inversal(x,y);}return 0;
}
——————————————————————施工现场的分割线———————————————————————
