LCT

· · 个人记录

辅助树内部用实边连接，辅助树之间用虚边连接，虚边总是由一棵$Splay$指向另一棵$Splay$的根，即为其中序遍历的第一个点 因为虚边是$Splay$之间相连，为保证其根不是其他节点的儿子，所以虚边只有父亲关系，没有儿子关系，而$Splay$之间的实边是同时具有父子关系 每一个$Splay$维护辅助树是一条从上到下按在原树中深度严格递增的路径，且中序遍历$Splay$得到的每个点的深度序列严格递增，即$Splay$中的节点$x$关键字为其在原树的深度 下列代码支持 删边加边 修改单点点权 查询连通性 查询路径点权权值和 ### 函数 $notroot:$ 判断节点$x$是否为其$Splay$的根 $access:$ 将节点$x$与原树的根通过$splay$操作到同一棵$Splay$中，即为节点$x$与原树的根的路径上全部变成实边 $makeroot:$ 将节点$x$变为原树的根 $split:$ 将节点$x$和节点$y$操作到同一棵$Splay$中，方便下一步操作 $code: 
bool check(int x)
{
    return ch[fa[x]][1]==x;
}
void pushrev(int x)
{
    rev[x]^=1,swap(ch[x][0],ch[x][1]);
}
void pushup(int x)
{
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
}
void pushdown(int x)
{
    if(!rev[x]) return;
    pushrev(ch[x][0]),pushrev(ch[x][1]);
    rev[x]=0;
}
bool notroot(int x)
{
    return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=check(x),w=ch[x][k^1];
    if(notroot(y)) ch[z][check(y)]=x;
    ch[x][k^1]=y,ch[y][k]=w;
    if(w) fa[w]=y;
    fa[x]=z,fa[y]=x;
    pushup(y),pushup(x);
}
void all(int x)
{
    if(notroot(x)) all(fa[x]);
    pushdown(x);
}
void splay(int x)
{
    all(x);
    for(int y;notroot(x);rotate(x))
        if(notroot(y=fa[x]))
            rotate(check(x)^check(y)?x:y);
    pushup(x);
}
void access(int x)
{
    for(int y=0;x;y=x,x=fa[x])
        splay(x),ch[x][1]=y,pushup(x);
}
void makeroot(int x)
{
    access(x),splay(x),pushrev(x);
}
void split(int x,int y)
{
    makeroot(x),access(y),splay(y);
}
int findroot(int x)
{
    access(x),splay(x);
    while(ch[x][0]) x=ch[x][0];
    splay(x);
    return x;
}
void link(int x,int y)
{
    makeroot(x);
    if(findroot(y)!=x) fa[x]=y;
}
void cut(int x,int y)
{
    makeroot(x);
    if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) 
        fa[y]=ch[x][1]=0;
}
int query(int x,int y)
{
    split(x,y);
    return sum[y];
}

若连边和删边合法

code: 
void link(int x,int y)
{
    split(x,y),fa[x]=y;
}
void cut(int x,int y)
{
    split(x,y),fa[x]=ch[y][0]=0;
}

维护子树信息

code: 
void pushup(int x)
{
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+s[x]+val[x];
}
void access(int x)
{
    for(int y=0;x;y=x,x=fa[x])
        splay(x),s[x]+=siz[ch[x][1]]-siz[ch[x][1]=y];
}
void link(int x,int y)
{
    split(x,y),s[fa[x]=y]+=siz[x];
}