LCT真是灵活好用…
LCT的基本思想与树链剖分差不多，都是把树剖成一条条链，只不过LCT用的是SPLAY维护的，而且，SPLAY的链是会变化的，不像剖分是定死的。
LCT最重要的操作就是access（有的地方叫expose），access(po)之后就把po到树的root这条路径变成一条链。
具体实现的话，直接向上一直连就行了，效率可以证明是O(lgn)的。
还有就是两个操作，link和cut。
cut不难，直接找到这条边断掉即可。
link的话，因为splay是用深度维护的，我们只需要access其中一个点，然后再将这个点打上翻转记号，这个点就会成为其所在的树的根，再将其接到另外一个点之下，就行了。
接下来是代码，因为前段时间BZ倒了，所以直接上的是伍一鸣的tree。
这题就是一个裸的LCT，splay上标记的打法与BZ的某道线段树题奇像。
Tsinsen1303/BZOJ2631
/**************************************************************
Problem: 2631
User: zhuohan123
Language: C++
Result: Accepted
Time:12260 ms
Memory:9836 kb
****************************************************************/ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
const int mod=;
int n,q;
struct node
{
int f,s[],ws,size;//splay tree
int head;//tree
bool rev;
uint num,sum,add,mul;
}p[];int pnum,root;
struct edge{int to,next;}g[];int gnum;
inline void addedge(int from,int to)
{
g[++gnum].to=to;g[gnum].next=p[from].head;p[from].head=gnum;
} inline void iadd(uint &x,uint y){x=(x+y)%mod;}
inline void imul(uint &x,uint y){x=(x*y)%mod;}
inline void modify(int po,uint m,uint a)
{
if(m!=)
{
imul(p[po].num,m);
imul(p[po].sum,m);
imul(p[po].mul,m);
imul(p[po].add,m);
}
if(a)
{
iadd(p[po].num,a);
iadd(p[po].sum,a*p[po].size%mod);
iadd(p[po].add,a);
}
}
inline void reverse(int po)
{
if(p[po].rev)
{
swap(p[po].s[],p[po].s[]);
if(p[po].s[])p[p[po].s[]].rev^=,p[p[po].s[]].ws^=;
if(p[po].s[])p[p[po].s[]].rev^=,p[p[po].s[]].ws^=;
p[po].rev^=;
}
}
inline void pushdown(int po)
{
if(p[po].mul!=||p[po].add!=)
{
if(p[po].s[])modify(p[po].s[],p[po].mul,p[po].add);
if(p[po].s[])modify(p[po].s[],p[po].mul,p[po].add);
p[po].mul=;p[po].add=;
}
}
inline void maintain(int po)
{
p[po].sum=p[po].num;
if(p[po].s[])iadd(p[po].sum,p[p[po].s[]].sum);
if(p[po].s[])iadd(p[po].sum,p[p[po].s[]].sum);
p[po].size=;
if(p[po].s[])p[po].size+=p[p[po].s[]].size;
if(p[po].s[])p[po].size+=p[p[po].s[]].size;
}
inline void setson(int f,int s,bool ws){p[f].s[ws]=s;p[s].f=f;p[s].ws=ws;}
inline bool isroot(int po)
{
return !p[po].f||(p[p[po].f].s[]!=po&&p[p[po].f].s[]!=po);
}
inline void rotate(int po,bool ws)
{
int son=p[po].s[ws];
if(isroot(po))p[son].f=p[po].f;
else setson(p[po].f,son,p[po].ws);
setson(po,p[son].s[!ws],ws);
setson(son,po,!ws);
maintain(po);maintain(son);
}
inline int splay(int po)
{
while(!isroot(po))
{
int fa=p[po].f,gf=p[fa].f;
reverse(gf);reverse(fa);reverse(po);
pushdown(gf);pushdown(fa);pushdown(po);
if(isroot(fa)){rotate(fa,p[po].ws);break;}
if(p[fa].ws==p[po].ws)rotate(gf,p[fa].ws);
rotate(fa,p[po].ws);
}
reverse(po);
pushdown(po);
maintain(po);
return po;
}
inline void access(int po)
{
for(int last=;po;last=po,po=p[po].f)
{
splay(po);
setson(po,last,);
maintain(po);
}
}
inline void makeroot(int po)
{
access(po);
splay(po);
p[po].rev^=;
}
inline void link(int u,int v)
{
makeroot(u);
p[u].f=v;
}
inline void cut(int u,int v)
{
access(v);
splay(u);
if(p[u].f==v)p[u].f=;
else
{
access(u);splay(v);
p[v].f=;
}
}
inline void change(int u,int v,uint m,uint a)
{
access(v);
for(int last=;u;last=u,u=p[u].f)
{
splay(u);
if(!p[u].f)
{
if(last)modify(last,m,a);
if(p[u].s[])modify(p[u].s[],m,a);
imul(p[u].num,m);
iadd(p[u].num,a);
}
setson(u,last,);
maintain(u);
}
}
inline uint getans(int u,int v)
{
access(v);
for(int last=;u;last=u,u=p[u].f)
{
splay(u);
if(!p[u].f)
{
uint ans=p[u].num;
if(last)iadd(ans,p[last].sum);
if(p[u].s[])iadd(ans,p[p[u].s[]].sum);
return ans;
}
setson(u,last,);
maintain(u);
}
}
void dfs(int po)
{
p[po].s[]=p[po].s[]=p[po].add=p[po].rev=;
p[po].num=p[po].sum=p[po].mul=p[po].size=;
for(int i=p[po].head;i;i=g[i].next)
if(g[i].to!=p[po].f)
{
p[g[i].to].f=po;
dfs(g[i].to);
}
}
int main(int argc, char *argv[])
{
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=;i<n;i++)
{
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
dfs();
while(q--)
{
char op[];scanf("%s",op);
if(op[]=='+')
{
int u,v,num;scanf("%d%d%d",&u,&v,&num);
change(u,v,,num%mod);
}
if(op[]=='*')
{
int u,v,num;scanf("%d%d%d",&u,&v,&num);
change(u,v,num%mod,);
}
if(op[]=='-')
{
int u1,v1,u2,v2;scanf("%d%d%d%d",&u1,&v1,&u2,&v2);
cut(u1,v1);link(u2,v2);
}
if(op[]=='/')
{
int u,v;scanf("%d%d",&u,&v);
printf("%d\n",getans(u,v));
}
}
return ;
}
还有一道是山东08年的省选题，就是LCT的模板题。
题意相当于维护一个带删除的并查集。
两个点是否在一个子树的判断，只需让两个点都一直沿着它的father跳，最后都会停在它所在的树的根所在的splay的根（好绕！！），只需判断这两个点是否相等即可。
BZOJ2049
/**************************************************************
Problem: 2049
User: zhuohan123
Language: C++
Result: Accepted
Time:1244 ms
Memory:4560 kb
****************************************************************/ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node{int f,s[];bool ws,rev;}p[];
inline bool isroot(int po){return (!p[po].f)||(p[p[po].f].s[]!=po&&p[p[po].f].s[]!=po);}
inline void setson(int f,int s,bool ws){p[s].f=f;p[f].s[ws]=s;p[s].ws=ws;}
inline void rotate(int po,bool ws)
{
int son=p[po].s[ws];
if(isroot(po))p[son].f=p[po].f;
else setson(p[po].f,son,p[po].ws);
setson(po,p[son].s[!ws],ws);
setson(son,po,!ws);
}
inline void reverse(int po)
{
if(p[po].rev)
{
swap(p[po].s[],p[po].s[]);
p[p[po].s[]].ws^=;
p[p[po].s[]].ws^=;
p[p[po].s[]].rev^=;
p[p[po].s[]].rev^=;
p[po].rev=false;
}
}
inline int splay(int po)
{
while(!isroot(po))
{
int fa=p[po].f,gf=p[fa].f;
reverse(gf);reverse(fa);reverse(po); if(isroot(fa)){rotate(fa,p[po].ws);break;}
if(p[fa].ws==p[po].ws)rotate(gf,p[fa].ws);
rotate(fa,p[po].ws);
}
reverse(po);
return po;
}
inline void access(int po)
{
for(int last=;po;last=po,po=p[po].f)
setson(splay(po),last,);
}
inline void makeroot(int po)
{
access(po);splay(po);
p[po].rev^=;
}
inline void link(int u,int v)
{
makeroot(u);p[u].f=v;
}
inline void cut(int u,int v)
{
access(u);splay(v);
if(p[v].f==u)p[v].f=;
else
{
access(v);splay(u);
p[u].f=;
}
}
inline bool check(int u,int v)
{
while(p[u].f)u=p[u].f;
while(p[v].f)v=p[v].f;
return u==v;
}
int main(int argc, char *argv[])
{
int n,m;scanf("%d%d",&n,&m);
while(m--)
{
char str[];int u,v;
scanf("%s%d%d",str,&u,&v);
if(str[]=='C')link(u,v);
if(str[]=='D')cut(u,v);
if(str[]=='Q')puts(check(u,v)?"Yes":"No");
}
return ;
}
接下来是最后一个……WC2006的水管局长
题意是维护一个带link与cut的最小生成树…
由于这棵树是会“动”的，所以不能把边权下放到点上，那么就只好把一条边变成一个点，再把这个点与两个端点相连，常数狂增不止。
BZOJ2494
/**************************************************************
Problem: 2594
User: zhuohan123
Language: C++
Result: Accepted
Time:15728 ms
Memory:53252 kb
****************************************************************/ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int getnum()
{
int ans=;char ch=getchar();
while(ch>''||ch<'')ch=getchar();
while(ch>=''&&ch<='')ans=ans*+ch-'',ch=getchar();
return ans;
}
int n,m,que;
struct point
{
int f,s[];bool ws,rev;
int num,mnum,mpos;
void output(int now)
{
printf("%d f:%d ls:%d rs:%d rev:%d num:%d mnum:%d mpos:%d\n",now,f,s[],s[],rev,num,mnum,mpos);
}
}p[];int pnum;
inline void maintain(int po)
{
p[po].mnum=p[po].num;p[po].mpos=po;
if(p[po].s[]&&p[p[po].s[]].mnum>p[po].mnum)
p[po].mnum=p[p[po].s[]].mnum,p[po].mpos=p[p[po].s[]].mpos;
if(p[po].s[]&&p[p[po].s[]].mnum>p[po].mnum)
p[po].mnum=p[p[po].s[]].mnum,p[po].mpos=p[p[po].s[]].mpos;
}
inline bool isroot(int po){return (!p[po].f)||(p[p[po].f].s[]!=po&&p[p[po].f].s[]!=po);}
inline void setson(int f,int s,bool ws){p[f].s[ws]=s;p[s].f=f;p[s].ws=ws;}
inline void rotate(int po,bool ws)
{
int son=p[po].s[ws];
if(isroot(po))p[son].f=p[po].f;
else setson(p[po].f,son,p[po].ws);
setson(po,p[son].s[!ws],ws);
setson(son,po,!ws);
maintain(po);maintain(son);
}
inline void reverse(int po)
{
if(p[po].rev)
{
swap(p[po].s[],p[po].s[]);
p[p[po].s[]].ws^=;
p[p[po].s[]].ws^=;
p[p[po].s[]].rev^=;
p[p[po].s[]].rev^=;
p[po].rev=false;
}
}
inline int splay(int po)
{
while(!isroot(po))
{
int fa=p[po].f,gf=p[fa].f;
reverse(gf);reverse(fa);reverse(po);
if(isroot(fa)){rotate(fa,p[po].ws);break;}
if(p[fa].ws==p[po].ws)rotate(gf,p[fa].ws);
rotate(fa,p[po].ws);
}
reverse(po);
return po;
}
inline void access(int po)
{
for(int last=;po;last=po,po=p[po].f)
{
splay(po);
setson(po,last,);
maintain(po);
}
}
inline void makeroot(int po)
{
access(po);splay(po);
p[po].rev^=;
}
inline void link(int u,int v)
{
makeroot(u);p[u].f=v;
}
inline void cut(int u,int v)
{
access(u);splay(v);
if(p[v].f==u)p[v].f=;
else
{
access(v);splay(u);
p[u].f=;
}
}
inline int getmax(int u,int v,int &mpos)
{
access(v);
for(int last=;u;last=u,u=p[u].f)
{
splay(u);
if(!p[u].f)
{
int ans=p[u].num;mpos=u;
if(p[u].s[]&&ans<p[p[u].s[]].mnum)ans=p[p[u].s[]].mnum,mpos=p[p[u].s[]].mpos;
if(last&&ans<p[last].mnum)ans=p[last].mnum,mpos=p[last].mpos;
return ans;
}
setson(u,last,);
maintain(u);
}
return ;
}
struct bian{int u,v,c,can;}b[];
inline bool cmp1(bian a,bian b){return a.u==b.u?a.v<b.v:a.u<b.u;}
inline bool cmp2(bian a,bian b){return a.c<b.c;}
struct question{int p,u,v,pos,c,ans;}q[];
inline bool cmp3(question a,question b){return a.u==b.u?a.v<b.v:a.u<b.u;}
inline bool cmp4(question a,question b){return a.pos<b.pos;}
int fa[];
int gf(int po){return fa[po]==po?po:fa[po]=gf(fa[po]);}
int head[];
struct edge{int to,next;}g[];int gnum;
inline void addedge(int from,int to)
{
g[++gnum].to=to;g[gnum].next=head[from];head[from]=gnum;
g[++gnum].to=from;g[gnum].next=head[to];head[to]=gnum;
}
bian intree[];
int qu[],ql,qr;
void bfs()
{
ql=;qr=;
qu[++qr]=;
while(ql<=qr)
for(int now=qu[ql++],i=head[now];i;i=g[i].next)
if(p[now].f!=g[i].to)
p[qu[++qr]=g[i].to].f=now;
}
int main(int argc, char *argv[])
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
n=getnum(),m=getnum(),que=getnum();
pnum=n;
for(int i=;i<=m;i++)
{
b[i].u=getnum(),b[i].v=getnum(),b[i].c=getnum();
if(b[i].u>b[i].v)swap(b[i].u,b[i].v);
b[i].can=true;
}
for(int i=;i<=que;i++)
{
q[i].p=getnum(),q[i].u=getnum(),q[i].v=getnum();
if(q[i].u>q[i].v)swap(q[i].u,q[i].v);
q[i].pos=i;
}
sort(b+,b+m+,cmp1);
sort(q+,q+que+,cmp3);
for(int i=,j=;i<=m&&j<=que;i++)
{
while(j<=que&&((q[j].u<b[i].u)||(q[j].u==b[i].u&&q[j].v<b[i].v)||q[j].p==))j++;
if(j<=que&&q[j].u==b[i].u&&q[j].v==b[i].v)b[i].can=false,q[j].c=b[i].c;
}
for(int i=;i<=n;i++)fa[i]=i;
sort(b+,b+m+,cmp2);
for(int i=;i<=m;i++)
if(b[i].can&&gf(b[i].u)!=gf(b[i].v))
{
pnum++;p[pnum].num=b[i].c;
addedge(b[i].u,pnum);
addedge(b[i].v,pnum);
intree[pnum].u=b[i].u;intree[pnum].v=b[i].v;
fa[gf(b[i].u)]=gf(b[i].v);
}
bfs();
for(int i=;i<=pnum;i++)p[i].mnum=p[i].num,p[i].mpos=i;
sort(q+,q+que+,cmp4);
for(int i=que;i;i--)
{
int mpos;
if(q[i].p==)q[i].ans=getmax(q[i].u,q[i].v,mpos);
else if(getmax(q[i].u,q[i].v,mpos)>q[i].c)
{
cut(mpos,intree[mpos].u);
cut(mpos,intree[mpos].v);
intree[mpos].u=q[i].u;
intree[mpos].v=q[i].v;
p[mpos].num=q[i].c;
link(mpos,q[i].u);
link(mpos,q[i].v);
}
}
for(int i=;i<=que;i++)
if(q[i].p==)printf("%d\n",q[i].ans);
return ;
}