这一篇重点探讨LCT的应用
例：bzoj 2631 tree2（国家集训队）
LCT模板操作之一，利用SPLAY可以进行区间操作这一性质对维护懒惰标记，注意标记下传顺序和如何下传
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define uint unsigned int
#define mode 51061
using namespace std;
uint c[100005][2];
uint v[100005];
uint s[100005];
uint alazy[100005];
uint mlazy[100005];
uint f[100005];
uint ttag[100005];
uint huge[100005];
uint n,m;
char ss[5];
bool berot(uint rt)
{
if(c[f[rt]][0]==rt||c[f[rt]][1]==rt)
{
return 0;
}
return 1;
}
void reverse(uint rt)
{
swap(c[rt][0],c[rt][1]);
ttag[rt]^=1;
}
void update(uint rt)
{
huge[rt]=huge[c[rt][0]]+huge[c[rt][1]]+1;
s[rt]=(s[c[rt][0]]+s[c[rt][1]]+v[rt])%mode;
}
void mul(uint rt,uint val)
{
s[rt]*=val;
s[rt]%=mode;
v[rt]*=val;
v[rt]%=mode;
alazy[rt]*=val;
alazy[rt]%=mode;
mlazy[rt]*=val;
mlazy[rt]%=mode;
}
void add(uint rt,uint val)
{
s[rt]+=val*huge[rt];
s[rt]%=mode;
alazy[rt]+=val;
alazy[rt]%=mode;
v[rt]+=val;
v[rt]%=mode;
}
void pushdown(uint rt)
{
if(mlazy[rt]!=1)
{
mul(c[rt][0],mlazy[rt]);
mul(c[rt][1],mlazy[rt]);
mlazy[rt]=1;
}
if(alazy[rt])
{
add(c[rt][0],alazy[rt]);
add(c[rt][1],alazy[rt]);
alazy[rt]=0;
}
if(ttag[rt])
{
if(c[rt][0])
{
reverse(c[rt][0]);
}
if(c[rt][1])
{
reverse(c[rt][1]);
}
ttag[rt]=0;
}
}
void repush(uint rt)
{
if(!berot(rt))
{
repush(f[rt]);
}
pushdown(rt);
}
void rotate(uint rt)
{
uint ltyp=0;
uint fa=f[rt];
uint ffa=f[fa];
if(c[fa][1]==rt)
{
ltyp=1;
}
if(!berot(fa))
{
if(c[ffa][0]==fa)
{
c[ffa][0]=rt;
}else
{
c[ffa][1]=rt;
}
}
c[fa][ltyp]=c[rt][ltyp^1];
c[rt][ltyp^1]=fa;
f[c[fa][ltyp]]=fa;
f[fa]=rt;
f[rt]=ffa;
update(fa);
}
void splay(uint rt)
{
repush(rt);
while(!berot(rt))
{
uint fa=f[rt];
uint ffa=f[fa];
if(!berot(fa))
{
if((c[fa][0]==rt&&c[ffa][0]!=fa)||(c[fa][1]==rt&&c[ffa][1]!=fa))
{
rotate(rt);
}else
{
rotate(fa);
}
}
rotate(rt);
}
update(rt);
}
void access(uint rt)
{
uint y=0;
while(rt)
{
splay(rt);
c[rt][1]=y;
update(rt);
y=rt;
rt=f[rt];
}
}
void makeroot(uint rt)
{
access(rt);
splay(rt);
reverse(rt);
}
void split(uint st,uint ed)
{
makeroot(st);
access(ed);
splay(ed);
}
void link(uint st,uint ed)
{
makeroot(st);
f[st]=ed;
}
void cut(uint st,uint ed)
{
split(st,ed);
f[st]=c[ed][0]=0;
}
inline uint read()
{
uint f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f =1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read(),m=read();
for(uint i=1;i<=n;i++)
{
huge[i]=1;
v[i]=1;
mlazy[i]=1;
}
for(uint i=1;i<n;i++)
{
uint x=read(),y=read();
link(x,y);
}
while(m--)
{
scanf("%s",ss);
if(ss[0]=='+')
{
uint x=read(),y=read(),z=read();
split(x,y);
add(y,z);
}else if(ss[0]=='-')
{
uint x=read(),y=read(),z=read(),q=read();
cut(x,y);
link(z,q);
}else if(ss[0]=='*')
{
uint x=read(),y=read(),z=read();
split(x,y);
mul(y,z);
}else
{
uint x=read(),y=read();
split(x,y);
printf("%u
",s[y]);
}
}
return 0;
}例：bzoj 3282 luogu 3690 link-cut-tree 模板
模板题，用SPLAY维护即可
注意判断加边的合法性
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
int c[400005][2];
ll s[400005];
int f[400005];
bool ttag[400005];
int v[400005];
int n,m;
bool berot(int rt)
{
if(c[f[rt]][0]==rt||c[f[rt]][1]==rt)
{
return 0;
}
return 1;
}
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void update(int rt)
{
s[rt]=(ll)s[c[rt][0]]^(ll)s[c[rt][1]]^(ll)v[rt];
}
void reverse(int rt)
{
swap(c[rt][0],c[rt][1]);
ttag[rt]^=1;
}
void pushdown(int rt)
{
if(ttag[rt])
{
if(c[rt][0])reverse(c[rt][0]);
if(c[rt][1])reverse(c[rt][1]);
ttag[rt]=0;
}
}
void repush(int rt)
{
if(!berot(rt))
{
repush(f[rt]);
}
pushdown(rt);
}
void rotate(int rt)
{
int ltyp=0;
int fa=f[rt];
int ffa=f[fa];
if(c[fa][1]==rt)
{
ltyp=1;
}
if(!berot(fa))
{
if(c[ffa][1]==fa)
{
c[ffa][1]=rt;
}else
{
c[ffa][0]=rt;
}
}
c[fa][ltyp]=c[rt][ltyp^1];
c[rt][ltyp^1]=fa;
f[c[fa][ltyp]]=fa;
f[fa]=rt;
f[rt]=ffa;
update(fa);
}
void splay(int rt)
{
repush(rt);
while(!berot(rt))
{
int fa=f[rt];
int ffa=f[fa];
if(!berot(fa))
{
if((c[fa][0]==rt&&c[ffa][0]!=fa)||(c[fa][1]==rt&&c[ffa][1]!=fa))
{
rotate(rt);
}else
{
rotate(fa);
}
}
rotate(rt);
}
update(rt);
}
void access(int rt)
{
int y=0;
while(rt)
{
splay(rt);
c[rt][1]=y;
update(rt);
y=rt;
rt=f[rt];
}
}
void makeroot(int rt)
{
access(rt);
splay(rt);
reverse(rt);
}
int getroot(int rt)
{
access(rt);
splay(rt);
while(c[rt][0])
{
pushdown(rt);
rt=c[rt][0];
}
return rt;
}
void link(int st,int ed)
{
makeroot(st);
if(getroot(ed)==st)
{
return;
}
f[st]=ed;
}
void cut(int st,int ed)
{
makeroot(ed);
if(getroot(st)==ed&&f[ed]==st&&!c[ed][1])
{
c[st][0]=f[ed]=0;
update(st);
}
}
void split(int st,int ed)
{
makeroot(st);
access(ed);
splay(ed);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
v[i]=read();
}
while(m--)
{
int typ=read(),x=read(),y=read();
if(typ==0)
{
split(x,y);
printf("%lld
",s[y]);
}else if(typ==1)
{
link(x,y);
}else if(typ==2)
{
cut(x,y);
}else
{
splay(x);
v[x]=y;
}
}
return 0;
}在上面两个模板应用中，有一个要点：repush！
在传递翻转标记时，我们要注意一定从上向下传标记！