最近一场的 ABC 的最后一题，官方题解介绍了一种基于 static top tree 的做法，虽然这个题明明可以直接用树链剖分。
然后我发现这个题解我读的并不是很懂，仔细复习了一下发现我之前对 top tree 的理解有误区。读了 negiizhao 的文章后认识到应该从历史文献中找线索，所以：
Top Tree: A top tree is a binary tree that embodies a contraction of a tree into a single edge via a sequence of rake and compress operations.
所以根据 Tarjan 的定义，Top Tree 一定是一个反应从独立的边开始反向通过 rake/compress 操作合并成单一簇的结构，也许类似思路的还有记录点分治过程形成的点分树，Kruskal 重构树还有划分树、Gomory–Hu Tree 这类结构。
当然关于 Link-Cut Tree、Top Tree 还有 ETT，现在因为具体实现的时候现在已经你中有我，我中有你，有的时候确实不好区分，可能对着代码说才更清晰，总之把这些容易混淆的概念解释清楚，也“是 OI 界水平普遍提高、命题规范完善和出题人的使命感和责任心增强的最好见证。” 囧。
参考资料
- Top Tree 相关理论扯淡
- SATT(Self-Adjusting Top Tree)学习笔记
- Self-Adjusting Top Trees, Robert E. Tarjan, Renato F. Werneck., 2005
- Implementation of Dynamic Trees with In-Subtree Operations, Tomasz Radzik, 1998
- 动态树问题及其应用, 袁昕颢, 2007
- 浅谈动态树的相关问题及简单拓展, 黄志翱, 2014
- 一种基于LCT的树上同色连通块维护算法, 任之洲, 2016
- 《基础圆方树练习题》命题报告, 范致远, 2019
- 浅谈静态 Top Tree 在树和广义串并联图上的应用, 程思元, 2023
