Problem
要求维护一棵树,在资磁LCT所有操作的同时,进行对子树的修改和查询操作。
Solution
Tarjan提出的解决方案是
黄志翱大神在论文中写的是
看过两篇论文的zky大神说这两者不是完全相同的
所以还是叫它吧(虽然我确实更喜欢这个名字)
可以看作是的一种改进,解决了不能触及子树的弱点,据说复杂度也是,只是常数巨大。
在上,维护实链,虚边只能通过虚子树的父指针连接。
在上,在维护实链的同时想办法维护子树,就可以达到目的了。
维护子树,显然可以在每个节点上记录一个平衡树存储所有的虚子树的根,在中切换实边对应在平衡树中的插入删除。然而这样会比较麻烦,因为每个节点同时存在两份数据,修改任意一个必须手动地让另一个同步。
翱犇在论文中给出了一种更巧妙的做法(来源于杜教?),记录四个子节点0,1,2,3,前两个还是维护链,后两个维护虚子树。如果通过某种手段可以让所有虚子树都处于叶节点,就可以直接链接过来而不会产生问题了。
做法和边分治比较类似:加入虚节点,把虚子树根的序列强制转成二叉树,就可以了。
注意的是,为了保证复杂度,维护虚子树的二叉树也需要,此时必须虚节点,转到真节点的下方。 会发现:一个真节点的2,3号子节点,维护的序列是完全不会有联系的,因为都是到真节点就停止了,不会到另一棵子树。这个不必困惑,因为首先这样做是不会让复杂度退化的,其次这样做可以使得对虚实节点的操作完全一视同仁,可以简化实现。