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)的时间内

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

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

HJWJBSR Avatar