LCT学习笔记(新文章暂时置顶,upd 2020.5.4)

本文持续更新中

0X00 前置知识

LCT 的前置知识有:Splay(网上有用 fhq-Treap 写 LCT 的方法,不主流,在这里不作讲解)

0X01 介绍

LCT(Link-Cut Tree),是一个 Splay 森林。Splay 之间用虚边连接,Splay 内部用实边连接。

LCT的一些经典操作有:

  • 连接树边 uvu\leftrightarrow v
  • 删除树边 uvu\leftrightarrow v
  • 链上操作,如修改、询问链上权值

0X02 基本定义

int fa[MAXN], v[MAXN], s[MAXN], tag[MAXN], st[MAXN], son[MAXN][2];

fa 存每个节点的父亲,v 是点权,s 是该点以及子树的权值和,tag 是该点的翻转情况,st 是一个栈,将在下文提到,son 存左右儿子。

0X03 基本操作

咕了

0XFF 参考文献

  1. 浅谈Link-Cut Tree