May 1, 2024
最近一场的 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 界水平普遍提高、命题规范完善和出题人的使命感和责任心增强的最好见证。” 囧。
Posted by
xiaodao
Category: 日常
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。