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)的时间内
但常数大而且代码复杂度高
欢迎质疑、提问或者提出改进的意见