mit 6.851 Advanced Data Structures L19 Dynamic Graphs I : Link-Cut Tree

视频链接

截图的笔记来源

主要思路是维护一个有根（无序）树的森林，保证每个操作的分摊复杂度为 $O(\log(n))$O(log(n))，用平衡树来表示不平衡树。

access(v) 是核心操作。笔记中有一个笔误，见图片中的箭头

有了 access 之后，其他函数都很好写。

开始对复杂度进行分析，核心是分析 access 的复杂度，首先给出了一个 $O(\log^2n)$O(log2n) 的界，这个界是通过重链剖分来得到的。

根据 splay 的势能分析法可以得到一个更紧的界：$O(\log{n})$O(logn)