关于LCT
查看原帖
关于LCT
365689
我是一个小号楼主2022/7/23 09:14

萌新 刚学OI 刚学LCT……然后发现有亿点点懵

以下是我几个(在大佬们眼中十分sb的)问题:

1.makeroot把深度翻转,似乎辅助树就和原树对不上了(也就是说这棵树似乎失真了变成另一棵树了),这样继续用辅助树来维护原树,不会有问题吗?

(当然我知道不会有问题的,但我还是不太明白,为什么这样改动辅助树的结构不会对结果产生影响)

2.LCT适用的范围是什么?是仅仅是森林吗?还是还能维护有环图?换句话说,搞个环用LCT跑,会不会崩掉?蒟蒻刚学LCT,还没弄清楚它如何应用。

(个人感觉有环是不行的,但LCT模板P3690似乎并没有保证不存在环,题解里面似乎也没有判环……)

3.LCT复杂度如何?看起来似乎常数很大的样子……

4.相比相似的数据结构(如树链剖分),LCT的优势在哪里?

(这个问题我个人的思考是,LCT是动态的,灵活的,能支持连边删边,但想问问还有没有别的)

2022/7/23 09:14
加载中...