LCT link cut tree 动态树模版题合集.doc

LCT link-cut-tree 动态树模版题合集by yusitongBzoj 2049加边、删边、查询所在联通块/*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 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-);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)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 加边、删边、查询到根的距离/*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=sizechx0+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(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);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);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); elsescanf(%d,&y);y=min(x+y,n+1);cut(x,nxtx);link(x,y);nxtx=y;return 0;Bzoj 3282加边、删边、单点修改，树链查询#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=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=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);chx1=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=xsumxvalxy;valx=y;return 0;/*0：后接两个整数（，），代表询问从到的路径上的点的权值的和。保证到是联通的。1：后接两个整数（，），代表连接到，若到已经联通则无需连接。：后接两个整数（，），代表删除边（，），不保证边（，）存在。：后接两个整数（，），代表将点上的权值变成。*/Bzoj2631加边、删边、树链上修改查询#include#include#include#define rep(i,l,r) for(int i=(l);i=(r);i+)using namespace std;const int INF=0x7fffffff;const int N = 110000;typedef long long LL;const LL Q = 51061;int n,q;int faN,sizeN,chN2;LL taN,tmN,sumN,valN;bool revN;int staN,top;#define RD readtemplate inline T read()T x=0,f=1;char t=getchar();while(t9|t=0&t=9)x=x*10+t-0,t=getchar();return x;bool isroot(int x)return chfax0!=x&chfax1!=x;void up(int x)sizex=(sizechx0+sizechx1+1)%Q;/!sumx=(sumchx0+sumchx1+valx)%Q;void cal(int id,LL m=1,LL a=0)if(!id)return;tmid=(tmid*m)%Q;taid=(taid*m+a)%Q;valid=(valid*m+a)%Q;sumid=(sumid*m+a*sizeid)%Q;void down(int x)int l=chx0,r=chx1;if(revx)revl=1;revr=1;swap(chx0,chx1);revx=0;if(tax=0&tmx=1)return;cal(l,tmx,tax);cal(r,tmx,tax);tmx=1;tax=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;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);chx1=t;/1!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;/ splay(x);/!yes!void cut(int x,int y)makeroot(x);access(y);splay(y);chy0=0;fax=0;up(x);int main()n=RD();q=RD();int u,v;rep(i,1,n)tmi=vali=sumi=sizei=1;rep(i,2,n)u=RD();v=RD(