LCT link cut tree 動(dòng)態(tài)樹模版題合集

1、LCT link-cut-tree 動(dòng)態(tài)樹模版題合集by yusitongBzoj 2049加邊、刪邊、查詢所在聯(lián)通塊/*Problem: 2049User: yusitongLanguage: C+Result: AcceptedTime:2036 msMemory:988 kb*/#include#include#includeusing namespace std;const int INF=0x7fffffff;const int N = 11000;int n,m;int faN,chN2;bool revN;int staN,top;bool isroot(int x)return

2、 chfax0!=x&chfax1!=x;void down(int x)if(!revx)return;revchx0=1;revchx1=1;swap(chx0,chx1);revx=0;void rotate(int x,int f)int y=fax;if(!isroot(y)chfaychfay1=y=x;fax=fay;if(chxf)fachxf=y;chy!f=chxf;fay=x;chxf=y;void splay(int x)sta+top=x;for(int i=x;!isroot(i);i=fai)sta+top=fai;while(top)down(statop-);

3、while(!isroot(x)if(!isroot(fax)if(chfax1=x)(chfafax1=fax)rotate(x,chfax0=x);else rotate(fax,chfafax0=fax);rotate(x,chfax0=x);void access(int x)int t=0;while(x)splay(x);chx1=t;t=x;x=fax;void makeroot(int x)access(x);splay(x);revx=1;void link(int x,int y)makeroot(x);fax=y;splay(x);void cut(int x,int y

4、)makeroot(x);access(y);splay(y);fax=0;chy0=0;int find(int x)access(x);splay(x);while(chx0)x=chx0;return x;int main()scanf(%d%d,&n,&m);char op10;int x,y;for(int i=1;i=m;i+)scanf(%s%d%d,op,&x,&y);if(op0=C)link(x,y);else if(op0=D)cut(x,y);elseputs(find(x)=find(y)?Yes:No);return 0;Bzoj2002 加邊、刪邊、查詢到根的距離

5、/*Problem: 2002User: yusitongLanguage: C+Result: AcceptedTime:2192 msMemory:5712 kb*/#include#include#includeusing namespace std;const int INF=0x7fffffff;const int N = 201000;int n,m;int faN,chN2,sizeN;bool revN;int nxtN;int staN,top;bool isroot(int x)return chfax0!=x&chfax1!=x;void up(int x)sizex=s

6、izechx0+sizechx1+1;void down(int x)if(!revx)return;revchx0=1;revchx1=1;revx=0;swap(chx0,chx1);void rotate(int x,int f)int y=fax;if(!isroot(y)chfaychfay1=y=x;fax=fay;if(chxf)fachxf=y;chy!f=chxf;fay=x;chxf=y;up(y);void splay(int x)sta+top=x;for(int i=x;!isroot(i);i=fai)sta+top=fai;while(top)down(stato

7、p-);while(!isroot(x)if(!isroot(fax)if(chfax0=x)(chfafax0=fax)rotate(x,chfax0=x);else rotate(fax,chfafax0=fax);rotate(x,chfax0=x);up(x);void access(int x)int t=0;while(x)splay(x);chx1=t;/ up(x);/?t=x;x=fax;void makeroot(int x)access(x);splay(x);revx=1;void link(int x,int y)makeroot(x);fax=y;splay(x);

8、void cut(int x,int y)makeroot(x);access(y);splay(y);fax=0;chy0=0;/up?int main()scanf(%d,&n);for(int i=1,t;i=n;i+) scanf(%d,&t);t=min(i+t,n+1);fai=nxti=t;sizei=1;sizen+1=1;scanf(%d,&m);int op,x,y;for(int i=1;i=m;i+)scanf(%d%d,&op,&x);x+;if(op=1)makeroot(n+1);access(x);splay(x);printf(%dn,sizechx0); e

9、lsescanf(%d,&y);y=min(x+y,n+1);cut(x,nxtx);link(x,y);nxtx=y;return 0;Bzoj 3282加邊、刪邊、單點(diǎn)修改，樹鏈查詢#include#include#includeusing namespace std;const int INF=0x7fffffff;const int N = 301000;int n,m;int faN,chN2,sizeN,valN,xsumN;bool revN;int staN,top;#define rep(i,l,r) for(int i=(l);i9|t=0&t=9)x=x*10+t-0,t

10、=getchar();return x*f;bool isroot(int x)return chfax0!=x&chfax1!=x;void up(int x)int l=chx0,r=chx1;xsumx=xsumlxsumrvalx;sizex=sizel+sizer+1;void down(int x)if(!revx)return;revchx0=1;revchx1=1;revx=0;swap(chx0,chx1);void rotate(int x,int f)int y=fax;if(!isroot(y)chfaychfay1=y=x;fax=fay;if(chxf)fachxf

11、=y;chy!f=chxf;fay=x;chxf=y;up(y);void splay(int x)sta+top=x;for(int i=x;!isroot(i);i=fai)sta+top=fai;while(top)down(statop-);while(!isroot(x)if(!isroot(fax)if(chfax0=x)(chfafax0=fax)rotate(x,chfax0=x);else rotate(fax,chfafax0=fax);rotate(x,chfax0=x);up(x);void access(int x)int t=0;while(x)splay(x);c

12、hx1=t;up(x);t=x;x=fax;void makeroot(int x)access(x);splay(x);revx=1;void split(int x,int y)makeroot(x);access(y);splay(y);void link(int x,int y)makeroot(x);fax=y;void cut(int x,int y)makeroot(x);access(y);splay(y);chy0=0;fax=0;up(y);int find(int x)access(x);splay(x);while(chx0)x=chx0;return x;int main()n=read();m=read();rep(i,1,n)xsumi=vali=read();sizei=1;int op,x,y;rep(i,1,m)op=read();x=read();y=read();if(op=0)split(x,y);printf(%dn,xsumy);else if(op=1)if(find(x)!=find(y)link(x,y);else if(op=2)if(find(x)=find(y)cut(x,y);elsemakeroot(x);xsumx=xsumxvalx