高度由习惯堆积

分类 数据结构:Link-Cut Tree 下的文章

BZOJ2759 一个动态树好题

题目有$N$个未知数$x[1..n]$和$N$个等式组成的同余方程组:$x[i]=k[i]*x[p[i]]+b[i] mod 10007$其中,$k[i],b[i],x[i]∈[0,10007)∩Z$你要应付$Q$个事务,每个是两种情况之一:一.询问当前$x[a]$的解$A\ a$无解输出-1$x[a]$有多解输出-2否则输出$x[a]$二.修改一个等式$C\ a\ k[a]\ p[a]\ ...

LCT的初步理解

用处LCT主要用于处理森林的问题,也就是处理点与点之间的断边和连边问题。它是以$Splay$为基础,均摊时间复杂度$O(nlogn)$的数据结构。它可以实现如下功能:连边断边换根路径修改路径查询它的实质是若干棵$Splay$,每棵$Splay$维护的是树上的某一条边($Splay$的中序遍历即为此路径从浅到深)实现有几篇好文章可供参考:PaulliantLCT总结——概念篇QTREE解法的一...