UOJ Logo HJWJBSR的博客

博客

ETT解决LCA及其拓展

2017-06-18 16:18:10 By HJWJBSR

Tarjan发明的ETT貌似不能够直接同时解决换根、Link、Cut和求LCA

那么是否能够加以改进呢?

然后就有了一些基于原来的ETT的一些想法:http://pan.baidu.com/s/1jH8UwDo

非常感谢@Duyixian 实现的代码:http://paste.ubuntu.com/24896682/

代码刚了几天确实不容易,写起来真的很恶心

具体内容可以看课件(为了方便就只挂出课件而不另外写博客了)

我们实现的ETT可以完成上述操作以及求某个点最远点、某个点最远点个数

我们觉得还可以做到可持久化、直径长度和直径条数的同时动态维护

以及可以解决经典的QTREE4问题(这个用TopTree能不能做到优秀的复杂度呢?)

在O(n log n)的时间内

但常数大而且代码复杂度高

欢迎质疑、提问或者提出改进的意见

评论

owen_creeper
%%%颂魔
ruanxingzhi
唉……颂膜还是太强了。
EtaoinWu
Tarjan发明的ETT貌似不能够直接同时解决换根、Link、Cut和求LCA 槽点:Tarjan发明的吗。。。然后为什么不行 话说有个idea:link-cut-换根-单点修改-(链/子树)(+-,对常数取min) 这个东西可以用treap beats做的吧,那么就可以扔到lct-ett上(超刺激的idea
HJWJBSR
@EtaoinWu QwQ论文资料都写了是Tarjan啊 行吧那说Tarjan是发明者之一应该没毛病了吧 说为啥不行求先看课件啊,,或者不如泥说说为啥能做吧 我们的认知中ETT就是维护树的欧拉序列或者DFS序,Tarjan老人家用的是前面一种 后面一种就算没有求LCA的单纯的动态树的操作也是无法完成的。 前面一种的动态树操作不加赘述 对于一颗静态树我们的欧拉序列求LCA当然就是给每条有向边附上边权+1/-1然后变成了+/- 1RMQ问题 但是Reroot还是会改变某些边是靠近还是远离根的状态(也就是边权) 而暴力修改复杂度是O(n)的,所以并不能直接做 Tarjan好像在论文里面强行写上了求LCA操作,但是动态树的操作并不全。 至于泥那个idea,,好像跟我这个做法没什么关系,只用ETT应该是不能做的。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。