LCT小结

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 <iostream>
 11 #include <cstdio>
 12 #include <cstring>
 13 #include <algorithm>
 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     else
133     {
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<n;i++)
188     {
189         int u,v;scanf("%d%d",&u,&v);
190         addedge(u,v);addedge(v,u);
191     }
192     dfs(1);
193     while(q--)
194     {
195         char op[5];scanf("%s",op);
196         if(op[0]=='+')
197         {
198             int u,v,num;scanf("%d%d%d",&u,&v,&num);
199             change(u,v,1,num%mod);
200         }
201         if(op[0]=='*')
202         {
203             int u,v,num;scanf("%d%d%d",&u,&v,&num);
204             change(u,v,num%mod,0);
205         }
206         if(op[0]=='-')
207         {
208             int u1,v1,u2,v2;scanf("%d%d%d%d",&u1,&v1,&u2,&v2);
209             cut(u1,v1);link(u2,v2);
210         }
211         if(op[0]=='/')
212         {
213             int u,v;scanf("%d%d",&u,&v);
214             printf("%d
",getans(u,v));
215         }
216     }
217     return 0;
218 }

还有一道是山东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 <iostream>
11 #include <cstdio>
12 #include <cstring>
13 #include <algorithm>
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     else
71     {
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 <iostream>
 11 #include <cstdio>
 12 #include <cstring>
 13 #include <algorithm>
 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
",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<p[p[u].s[1]].mnum)ans=p[p[u].s[1]].mnum,mpos=p[p[u].s[1]].mpos;
114             if(last&&ans<p[last].mnum)ans=p[last].mnum,mpos=p[last].mpos;
115             return ans;
116         }
117         setson(u,last,1);
118         maintain(u);
119     }
120     return 0; 
121 }
122 struct bian{int u,v,c,can;}b[1100000];
123 inline bool cmp1(bian a,bian b){return a.u==b.u?a.v<b.v:a.u<b.u;}
124 inline bool cmp2(bian a,bian b){return a.c<b.c;}
125 struct question{int p,u,v,pos,c,ans;}q[110000];
126 inline bool cmp3(question a,question b){return a.u==b.u?a.v<b.v:a.u<b.u;}
127 inline bool cmp4(question a,question b){return a.pos<b.pos;}
128 int fa[210000];
129 int gf(int po){return fa[po]==po?po:fa[po]=gf(fa[po]);}
130 int head[510000];
131 struct edge{int to,next;}g[1100000];int gnum;
132 inline void addedge(int from,int to)
133 {
134     g[++gnum].to=to;g[gnum].next=head[from];head[from]=gnum;
135     g[++gnum].to=from;g[gnum].next=head[to];head[to]=gnum;
136 }
137 bian intree[310000];
138 int qu[510000],ql,qr;
139 void bfs()
140 {
141     ql=1;qr=0;
142     qu[++qr]=1;
143     while(ql<=qr)
144         for(int now=qu[ql++],i=head[now];i;i=g[i].next)
145         if(p[now].f!=g[i].to)
146         p[qu[++qr]=g[i].to].f=now;
147 }
148 int main(int argc, char *argv[])
149 {
150     //freopen("1.in","r",stdin);
151     //freopen("1.out","w",stdout);
152     n=getnum(),m=getnum(),que=getnum();
153     pnum=n;
154     for(int i=1;i<=m;i++)
155     {
156         b[i].u=getnum(),b[i].v=getnum(),b[i].c=getnum();
157         if(b[i].u>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<b[i].u)||(q[j].u==b[i].u&&q[j].v<b[i].v)||q[j].p==1))j++;
171         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;
172     }
173     for(int i=1;i<=n;i++)fa[i]=i;
174     sort(b+1,b+m+1,cmp2);
175     for(int i=1;i<=m;i++)
176     if(b[i].can&&gf(b[i].u)!=gf(b[i].v))
177     {
178         pnum++;p[pnum].num=b[i].c;
179         addedge(b[i].u,pnum);
180         addedge(b[i].v,pnum);
181         intree[pnum].u=b[i].u;intree[pnum].v=b[i].v;
182         fa[gf(b[i].u)]=gf(b[i].v);
183     }
184     bfs();
185     for(int i=1;i<=pnum;i++)p[i].mnum=p[i].num,p[i].mpos=i;
186     sort(q+1,q+que+1,cmp4);
187     for(int i=que;i;i--)
188     {
189         int mpos;
190         if(q[i].p==1)q[i].ans=getmax(q[i].u,q[i].v,mpos);
191         else if(getmax(q[i].u,q[i].v,mpos)>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
",q[i].ans);
204     return 0;
205 }