LCT模板
#include#include #include #define lch ch[root][0]#define rch ch[root][1]#define fat fa[root]using namespace std;const int Maxn=1100000;int size[Maxn],fa[Maxn],ch[Maxn][2],flag[Maxn],st[Maxn],top;inline void update(int root) { size[root]=size[lch]+size[rch]+1;}inline int isroot(int root) { return ch[fat][0]==root||ch[fat][1]==root;}inline int son(int root) { return ch[fat][1]==root;}inline void pushr(int root) { flag[root]^=1; swap(lch,rch);}inline void pushdown(int root) { if(flag[root]) { flag[root]^=1; pushr(lch); pushr(rch); }}int min(int root) { pushdown(root); if(lch) return min(lch); return root;}void rotate(int root) { int y=fat,z=fa[y]; if(isroot(z)) ch[z][son(y)]=root; int d=son(root),x=ch[root][d^1]; ch[y][d]=x; fa[y]=root; fa[root]=z; if(x) fa[x]=y; ch[root][d^1]=y; update(y);}void splay(int root) { top=0; int temp=root; while(isroot(temp)) st[++top]=temp,temp=fa[temp]; for(int i=top;i>=1;i--) pushdown(st[i]); while(isroot(root)) { if(isroot(fat)) rotate(son(root)==son(fat)?fat:root); rotate(root); }update(root);}void access(int root) { for(int i=0;root;root=fa[i=root]) splay(root),rch=i,update(root);}void makeroot(int root) { access(root); splay(root); pushr(root);}int findroot(int root) { access(root); splay(root); int temp=min(root); return temp;}void split(int root,int y) { makeroot(root); access(y); splay(y);}void link(int root,int y) { makeroot(root); if(findroot(y)!=root) fat=y;}void cut(int root,int y) { makeroot(root); if(findroot(y)==root&&fat==y&&rch==0) fat=ch[y][0]=0,update(y);}int main() { return 0;}
lct通过维护若干棵splay来维护树上的若干条链，进而对链进行查询和修改。在不同的链之间，以单向的边链接，即只记父亲，不记儿子。
son：询问该节点是其父节点的哪个儿子。
isroot：若该点是对应了一条链的splay的根，则返回1，否则返回0。
pushr：子树翻转。
splay：将当前节点旋转至对应的一条链的splay的根处。
min：返回子树中最左一点。
access：将当前节点与根节点连成一条链。
makeroot：将当前节点变为根。方法为先access当前点后当前点与根节点处于一颗splay中，然后将当前点旋到根，翻转整颗树，则当前点变为根节点。
split：提取出root到y的链。
link：在root与y之间连边。
cut：将root与y之间的边断开。