LCT (Link-cut-tree)

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的板子搞一下

全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务