文章目录

LCT

快退役了学一波以前听过很多次但没时间学的东西

LCT定义

学习资料

建议读论文

  1. 维基百科 https://en.wikipedia.org/wiki/Link/cut_tree
  2. 论文 https://wenku.baidu.com/view/75906f160b4e767f5acfcedb
  3. 带图的博客 https://blog.csdn.net/attack666/article/details/80854225

四种操作

  1. Access
  2. Findroot
  3. cut
  4. link
    每个操作的复杂度分析都是log(n)

解决的问题

例题

  1. Spoj 375 Qtree
    本题中树是固定的不变的，实际上树剖足够了，但是也可以套LCT的板子搞一下