Link-Cut Tree

概念：Link-Cut Tree（LCT）用多棵伸展树维护动态森林的首选路径，支持连边、断边、换根和路径信息查询，适合在线树结构变化。

关键步骤

access(x) 将根到 x 的路径变为首选路径；makeroot(x) 在 access 后翻转路径；连边前换根，断边时暴露路径并切断相应儿子。结点须维护翻转标记并在旋转前下推。

void makeroot(int x){ access(x); splay(x); rev[x]^=1; }
int findroot(int x){
    access(x); splay(x); pushAll(x);
    while(ch[x][0]) x=ch[x][0],push(x);
    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); access(y); splay(y);
    if(ch[y][0]==x && !ch[x][1]) ch[y][0]=fa[x]=0;
}

复杂度

在标准实现和均摊分析下，各基础操作为 O(log n) 均摊，空间 O(n)。LCT 实现细节复杂，需严格维护父指针、懒标记和辅助树根判定。