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

1 /**************************************************************  2     Problem: 2631  3     User: zhuohan123  4     Language: C++  5     Result: Accepted  6     Time:12260 ms  7     Memory:9836 kb  8 ****************************************************************/  9   10 #include 
     
       11 #include 
      
        12 #include 
       
         13 #include 
        
          14 using namespace std; 15 typedef unsigned int uint; 16 const int mod=51061; 17 int n,q; 18 struct node 19 { 20     int f,s[2],ws,size;//splay tree 21     int head;//tree 22     bool rev; 23     uint num,sum,add,mul; 24 }p[110000];int pnum,root; 25 struct edge{
   int to,next;}g[210000];int gnum; 26 inline void addedge(int from,int to) 27 { 28     g[++gnum].to=to;g[gnum].next=p[from].head;p[from].head=gnum; 29 } 30   31 inline void iadd(uint &x,uint y){x=(x+y)%mod;} 32 inline void imul(uint &x,uint y){x=(x*y)%mod;} 33 inline void modify(int po,uint m,uint a) 34 { 35     if(m!=1) 36     { 37         imul(p[po].num,m); 38         imul(p[po].sum,m); 39         imul(p[po].mul,m); 40         imul(p[po].add,m); 41     } 42     if(a) 43     { 44         iadd(p[po].num,a); 45         iadd(p[po].sum,a*p[po].size%mod); 46         iadd(p[po].add,a); 47     } 48 } 49 inline void reverse(int po) 50 { 51     if(p[po].rev) 52     { 53         swap(p[po].s[0],p[po].s[1]); 54         if(p[po].s[0])p[p[po].s[0]].rev^=1,p[p[po].s[0]].ws^=1; 55         if(p[po].s[1])p[p[po].s[1]].rev^=1,p[p[po].s[1]].ws^=1; 56         p[po].rev^=1; 57     } 58 } 59 inline void pushdown(int po) 60 { 61     if(p[po].mul!=1||p[po].add!=0) 62     { 63         if(p[po].s[0])modify(p[po].s[0],p[po].mul,p[po].add); 64         if(p[po].s[1])modify(p[po].s[1],p[po].mul,p[po].add); 65         p[po].mul=1;p[po].add=0; 66     } 67 } 68 inline void maintain(int po) 69 { 70     p[po].sum=p[po].num; 71     if(p[po].s[0])iadd(p[po].sum,p[p[po].s[0]].sum); 72     if(p[po].s[1])iadd(p[po].sum,p[p[po].s[1]].sum); 73     p[po].size=1; 74     if(p[po].s[0])p[po].size+=p[p[po].s[0]].size; 75     if(p[po].s[1])p[po].size+=p[p[po].s[1]].size; 76 } 77 inline void setson(int f,int s,bool ws){p[f].s[ws]=s;p[s].f=f;p[s].ws=ws;} 78 inline bool isroot(int po) 79 { 80     return !p[po].f||(p[p[po].f].s[0]!=po&&p[p[po].f].s[1]!=po); 81 } 82 inline void rotate(int po,bool ws) 83 { 84     int son=p[po].s[ws]; 85     if(isroot(po))p[son].f=p[po].f; 86     else setson(p[po].f,son,p[po].ws); 87     setson(po,p[son].s[!ws],ws); 88     setson(son,po,!ws); 89     maintain(po);maintain(son); 90 } 91 inline int splay(int po) 92 { 93     while(!isroot(po)) 94     { 95         int fa=p[po].f,gf=p[fa].f; 96         reverse(gf);reverse(fa);reverse(po); 97         pushdown(gf);pushdown(fa);pushdown(po); 98         if(isroot(fa)){rotate(fa,p[po].ws);break;} 99         if(p[fa].ws==p[po].ws)rotate(gf,p[fa].ws);100         rotate(fa,p[po].ws);101     }102     reverse(po);103     pushdown(po);104     maintain(po);105     return po;106 }107 inline void access(int po)108 {109     for(int last=0;po;last=po,po=p[po].f)110     {111         splay(po);112         setson(po,last,1);113         maintain(po);114     }115 }116 inline void makeroot(int po)117 {118     access(po);119     splay(po);120     p[po].rev^=1;121 }122 inline void link(int u,int v)123 {124     makeroot(u);125     p[u].f=v;126 }127 inline void cut(int u,int v)128 {129     access(v);130     splay(u);131     if(p[u].f==v)p[u].f=0;132     else133     {134         access(u);splay(v);135         p[v].f=0;136     }137 }138 inline void change(int u,int v,uint m,uint a)139 {140     access(v);141     for(int last=0;u;last=u,u=p[u].f)142     {143         splay(u);144         if(!p[u].f)145         {146             if(last)modify(last,m,a);147             if(p[u].s[1])modify(p[u].s[1],m,a);148             imul(p[u].num,m);149             iadd(p[u].num,a);150         }151         setson(u,last,1);152         maintain(u);153     }154 }155 inline uint getans(int u,int v)156 {157     access(v);158     for(int last=0;u;last=u,u=p[u].f)159     {160         splay(u);161         if(!p[u].f)162         {163             uint ans=p[u].num;164             if(last)iadd(ans,p[last].sum);165             if(p[u].s[1])iadd(ans,p[p[u].s[1]].sum);166             return ans;167         }168         setson(u,last,1);169         maintain(u);170     }171 }172 void dfs(int po)173 {174     p[po].s[0]=p[po].s[1]=p[po].add=p[po].rev=0;175     p[po].num=p[po].sum=p[po].mul=p[po].size=1;176     for(int i=p[po].head;i;i=g[i].next)177         if(g[i].to!=p[po].f)178         {179             p[g[i].to].f=po;180             dfs(g[i].to);181         }182 }183 int main(int argc, char *argv[])184 {185     //freopen("1.in","r",stdin);freopen("1.out","w",stdout);186     scanf("%d%d",&n,&q);187     for(int i=1;i
        
       
      
     

还有一道是山东08年的省选题，就是LCT的模板题。

题意相当于维护一个带删除的并查集。

两个点是否在一个子树的判断，只需让两个点都一直沿着它的father跳，最后都会停在它所在的树的根所在的splay的根（好绕！！），只需判断这两个点是否相等即可。

BZOJ2049

1 /************************************************************** 2     Problem: 2049 3     User: zhuohan123 4     Language: C++ 5     Result: Accepted 6     Time:1244 ms 7     Memory:4560 kb 8 ****************************************************************/ 9  10 #include 
     
      11 #include 
      
       12 #include 
       
        13 #include 
        
         14 using namespace std;15 struct node{
   int f,s[2];bool ws,rev;}p[210000];16 inline bool isroot(int po){
   return (!p[po].f)||(p[p[po].f].s[0]!=po&&p[p[po].f].s[1]!=po);}17 inline void setson(int f,int s,bool ws){p[s].f=f;p[f].s[ws]=s;p[s].ws=ws;}18 inline void rotate(int po,bool ws)19 {20     int son=p[po].s[ws];21     if(isroot(po))p[son].f=p[po].f;22     else setson(p[po].f,son,p[po].ws);23     setson(po,p[son].s[!ws],ws);24     setson(son,po,!ws);25 }26 inline void reverse(int po)27 {28     if(p[po].rev)29     {30         swap(p[po].s[0],p[po].s[1]);31         p[p[po].s[0]].ws^=1;32         p[p[po].s[1]].ws^=1;33         p[p[po].s[0]].rev^=1;34         p[p[po].s[1]].rev^=1;35         p[po].rev=false;36     }37 }38 inline int splay(int po)39 {40     while(!isroot(po))41     {42         int fa=p[po].f,gf=p[fa].f;43         reverse(gf);reverse(fa);reverse(po);44          45         if(isroot(fa)){rotate(fa,p[po].ws);break;}46         if(p[fa].ws==p[po].ws)rotate(gf,p[fa].ws);47         rotate(fa,p[po].ws);48     }49     reverse(po);50     return po;51 }52 inline void access(int po)53 {54     for(int last=0;po;last=po,po=p[po].f)55         setson(splay(po),last,1);56 }57 inline void makeroot(int po)58 {59     access(po);splay(po);60     p[po].rev^=1;61 }62 inline void link(int u,int v)63 {64     makeroot(u);p[u].f=v;65 }66 inline void cut(int u,int v)67 {68     access(u);splay(v);69     if(p[v].f==u)p[v].f=0;70     else71     {72         access(v);splay(u);73         p[u].f=0;74     }75 }76 inline bool check(int u,int v)77 {78     while(p[u].f)u=p[u].f;79     while(p[v].f)v=p[v].f;80     return u==v;81 }82 int main(int argc, char *argv[])83 {84     int n,m;scanf("%d%d",&n,&m);85     while(m--)86     {87         char str[30];int u,v;88         scanf("%s%d%d",str,&u,&v);89         if(str[0]=='C')link(u,v);90         if(str[0]=='D')cut(u,v);91         if(str[0]=='Q')puts(check(u,v)?"Yes":"No");92     }93     return 0;94 }
        
       
      
     

 接下来是最后一个……WC2006的水管局长

题意是维护一个带link与cut的最小生成树…

由于这棵树是会“动”的，所以不能把边权下放到点上，那么就只好把一条边变成一个点，再把这个点与两个端点相连，常数狂增不止。

BZOJ2494

1 /**************************************************************  2     Problem: 2594  3     User: zhuohan123  4     Language: C++  5     Result: Accepted  6     Time:15728 ms  7     Memory:53252 kb  8 ****************************************************************/  9   10 #include 
     
       11 #include 
      
        12 #include 
       
         13 #include 
        
          14 using namespace std; 15 inline int getnum() 16 { 17     int ans=0;char ch=getchar(); 18     while(ch>'9'||ch<'0')ch=getchar(); 19     while(ch>='0'&&ch<='9')ans=ans*10+ch-'0',ch=getchar(); 20     return ans; 21 } 22 int n,m,que; 23 struct point 24 { 25     int f,s[2];bool ws,rev; 26     int num,mnum,mpos; 27     void output(int now) 28     { 29         printf("%d f:%d ls:%d rs:%d rev:%d num:%d mnum:%d mpos:%d\n",now,f,s[0],s[1],rev,num,mnum,mpos); 30     } 31 }p[510000];int pnum; 32 inline void maintain(int po) 33 { 34     p[po].mnum=p[po].num;p[po].mpos=po; 35     if(p[po].s[1]&&p[p[po].s[1]].mnum>p[po].mnum) 36         p[po].mnum=p[p[po].s[1]].mnum,p[po].mpos=p[p[po].s[1]].mpos; 37     if(p[po].s[0]&&p[p[po].s[0]].mnum>p[po].mnum) 38         p[po].mnum=p[p[po].s[0]].mnum,p[po].mpos=p[p[po].s[0]].mpos; 39 } 40 inline bool isroot(int po){
   return (!p[po].f)||(p[p[po].f].s[0]!=po&&p[p[po].f].s[1]!=po);} 41 inline void setson(int f,int s,bool ws){p[f].s[ws]=s;p[s].f=f;p[s].ws=ws;} 42 inline void rotate(int po,bool ws) 43 { 44     int son=p[po].s[ws]; 45     if(isroot(po))p[son].f=p[po].f; 46     else setson(p[po].f,son,p[po].ws); 47     setson(po,p[son].s[!ws],ws); 48     setson(son,po,!ws); 49     maintain(po);maintain(son); 50 } 51 inline void reverse(int po) 52 { 53     if(p[po].rev) 54     { 55         swap(p[po].s[0],p[po].s[1]); 56         p[p[po].s[0]].ws^=1; 57         p[p[po].s[1]].ws^=1; 58         p[p[po].s[0]].rev^=1; 59         p[p[po].s[1]].rev^=1; 60         p[po].rev=false; 61     } 62 } 63 inline int splay(int po) 64 { 65     while(!isroot(po)) 66     { 67         int fa=p[po].f,gf=p[fa].f; 68         reverse(gf);reverse(fa);reverse(po); 69         if(isroot(fa)){rotate(fa,p[po].ws);break;} 70         if(p[fa].ws==p[po].ws)rotate(gf,p[fa].ws); 71         rotate(fa,p[po].ws); 72     } 73     reverse(po); 74     return po; 75 } 76 inline void access(int po) 77 { 78     for(int last=0;po;last=po,po=p[po].f) 79     { 80         splay(po); 81         setson(po,last,1); 82         maintain(po); 83     } 84 } 85 inline void makeroot(int po) 86 { 87     access(po);splay(po); 88     p[po].rev^=1; 89 } 90 inline void link(int u,int v) 91 { 92     makeroot(u);p[u].f=v; 93 } 94 inline void cut(int u,int v) 95 { 96     access(u);splay(v); 97     if(p[v].f==u)p[v].f=0; 98     else 99     {100         access(v);splay(u);101         p[u].f=0;102     }103 }104 inline int getmax(int u,int v,int &mpos)105 {106     access(v);107     for(int last=0;u;last=u,u=p[u].f)108     {109         splay(u);110         if(!p[u].f)111         {112             int ans=p[u].num;mpos=u;113             if(p[u].s[1]&&ans
         
          b[i].v)swap(b[i].u,b[i].v);158         b[i].can=true;159     }160     for(int i=1;i<=que;i++)161     {162         q[i].p=getnum(),q[i].u=getnum(),q[i].v=getnum();163         if(q[i].u>q[i].v)swap(q[i].u,q[i].v);164         q[i].pos=i;165     }166     sort(b+1,b+m+1,cmp1);167     sort(q+1,q+que+1,cmp3);168     for(int i=1,j=1;i<=m&&j<=que;i++)169     {170         while(j<=que&&((q[j].u
          
           
            q[i].c)192 {193 cut(mpos,intree[mpos].u);194 cut(mpos,intree[mpos].v);195 intree[mpos].u=q[i].u;196 intree[mpos].v=q[i].v;197 p[mpos].num=q[i].c;198 link(mpos,q[i].u);199 link(mpos,q[i].v);200 }201 }202 for(int i=1;i<=que;i++)203 if(q[i].p==1)printf("%d\n",q[i].ans);204 return 0;205 }