Link Cut Tree

概述

Link Cut Tree 简称 LCT，用一组 Splay 维护一片森林的实链剖分，支持在线的连边、断边、换根，以及链上的修改与查询。核心操作 access 把某点到所在树根的路径拉成一条实链、对应一棵 Splay；在此之上实现 makeroot、link、cut、split 等接口，分别完成换根、连边、断边与取出一条路径。所有操作的均摊复杂度为对数级。它相当于树链剖分的动态版本，适合处理树形态会不断改变、需要动态维护连通性与路径信息的问题。附 P3690 作为模板例题。

参考资料

• Link Cut Tree - OI Wiki

简介

Link Cut Tree（LCT）用一组 Splay 维护一片森林的 实链剖分，支持在线的连边、断边、换根，以及链上的修改与查询。

核心操作 access(u) 把 $u$ 到所在树根的路径变成一条实链（对应一棵 Splay）；在此之上实现 makeroot、link、cut、split 等。所有操作的均摊复杂度为 $O(\log n)$。它是树链剖分的动态版本，适合处理树形态会改变的问题。

例题

洛谷 P3690 【模板】动态树（LCT）

维护一个 $n$ 个点带权的森林，支持四种操作：查询某条路径上所有点权的异或和、连边、断边、修改点权（保证操作合法）。