如果你 不幸 点进来了那就别走了。
给我一分钟，我将讲懂 ETT。
首先，有个喜闻乐见的东西叫欧拉序。
如果忘了建议想一想 \(LCA\) 问题是怎么转化成 \(RMQ\) 的。
现在，我们对着一棵树跑 \(DFS\)，然后每次经过 一条边或一个点 就把这个东西放到序列末尾。
但是注意一个点只放进去一次，就是进入的时候。
然后得到的序列就是欧拉序了。
现在我们考虑如何用这个东西进行奇妙操作。
- 换根。我们发现欧拉序是一个环，所以直接把序列的前半部分扔到后面。
- 连边。考虑直接把其中一棵树的 \(DFN\) 序割开，把第二颗树的 \(DFN\) 序放进去，然后再加上两个边。
- 删边。同理。
上面这些用 fhq treap 可以轻松维护。
好了你现在已经学会 ETT 了。
说是这么说，实际打起来其实需要考虑的还不少。
然后一些其他操作，比如维护子树信息，就直接转成序列操作。
本来想用一个下午的时间学一样东西来着。
然后发现根本没东西。
今天接着摆。