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