• 周四. 8月 11th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

虚树 笔记

admin

11月 28, 2021

虚树 笔记

以前就学过虚树,但那是在初三的大规模反攻whk以前。

于是现在就是嘴巴说会,手说不会的状态。我大概还记得就是拿栈维护一条链,但是具体咋写已经完全不懂了

于是这篇侧重代码实现与应用

虚树是啥

对于树上的 (k) 个关键点,我们要维护路径信息/做决策等,很多时候我们发现,只有这些点和它们的 LCA​ 是有用的。而我们可以证明,算上 LCA,一共也不会超过 (2k) 个点。

于是我们可以把这些关键点 “提取” 出来,父子关系按照原树上的祖先关系重新建立。

虚树就是“提取”这样一个东西的算法,时间是 (O(klog k)),严格不和 (n) 有关。

如何搞

脑补一下,我们可以按 DFS 序排序,然后一个一个的加进来。每个东西加进来的时候,想象一下,它肯定是啪的一下,接到一条链的某个位置下面。然后我们拿栈维护这个链就行了。

更加具体的讲解见 oi-wiki

由于我现在非常困,所以我不想再讲一遍= =

实现的注意/技巧

这个是很重要的。

  1. 先把树结构搞定。可以直接拿样例看建出来的虚树结构对不对,最好手捏数据 (用草稿纸)
  2. 注意“悬在中间的关键点”,很容易挂在这里 —— 不要以为关键点都在叶子上!
  3. 平常打板可以选择消耗战那个题;大工程那个题,似乎确凿是个大工程,不太好写
  4. 注意加入栈时候的连边顺序,拿脑子想清楚,或者画一画

考场的话,虚树还是一个不太好打出来的东西;花多点时间拍,心态不要乱,有的时候,一个100比两个暴力来的赚。

还有就是可以研究一下有没有比较好写的写法。

发表评论

您的电子邮箱地址不会被公开。