[ZJOI2008]树的统计Count
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include
[sdoi2011] 染色
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include
[SDOI2008]洞穴勘测
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include
[hnoi2010]弹飞绵羊
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include
上面是这两天写的四道题代码；
敲了几天的LCT代码，感觉不错，决定写个总结；
LCT可以动态维护某点到根的某些数据；
方法：将树剖成一条条链，每条链用一个splay维护，这样查询的时候，顺着链向上以深度为关键字合并splay，这样在最后的splay上就可以查询某些信息；
首先需要构造一棵splay：
void updata(int x){ //需要维护的信息}void pushdown(int x){ //需要下传的标记}bool isroot(int x){ return c[fa[x]][1]!=x&&c[fa[x]][0]!=x;}void rotate(int x){ int d,y=fa[x],z=fa[y]; d=(c[y][1]==x); if(!isroot(y))c[z][c[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[c[x][d^1]]=y; c[y][d]=c[x][d^1];c[x][d^1]=y; updata(y);updata(x);}void splay(int x){ q[++top]=x; for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i]; while(top)pushdown(q[top--]); while(!isroot(x)){ int y=fa[x],z=fa[y]; if(!isroot(y)){ if((c[y][1]==x)^(c[z][1]==y))rotate(y); else rotate(x); } rotate(x); }} 操作1：access（LCT的核心操作）：
void access(int x){for(int t=0;x;t=x,x=fa[x])splay(x),c[x][1]=t,updata(x);} 操作2：makeroot（使某个点成为所在树的根，实际是splay翻转）：
void makeroot(int x){access(x);splay(x);rev[x]^=1;} 需要注意的是，有些题目中需要维护的信息与左右子树的位置有关，打rev标机的时候注意；
这个操作比较方便，但可以不使用；
操作3：link（连接两棵树）：
void link(int x,int y){makeroot(x);fa[x]=y;splay(x);} 也有其他写法；
操作4：cut（断开两个树）：
void cut(int x,int y){makeroot(x);access(y);splay(x);c[x][1]=fa[y]=0;} 时间上：
LCT的常数大（主要是splay），但很灵活，很多无良出题人喜欢卡LCT；
树链剖分不能动态维护信息；