虚树

· · 个人记录

构造方法

考虑这样一类问题，给一棵树 T,以及一个点集 S ,答案只与点集之间的关系有关。

为了方便讨论, S 是一个以 dfs 序为关键字从小到大排序的有序集合。

我们只会留下绿圈的点，这就是虚树的思想。

可是还有很多点不是关键点呀？

没错，将一条条链合并，这样保证了我们建出来的虚树大小规模是 |S| 级别的。

压缩方法基于下面这个性质：

\{\text{lca}(u,v) | u \in \text{S},v\in \text{S}\}= \{\text{lca}(u_i,u_{i+1\bmod |\text{S}|}) | u\in \text{S},v\in \text{S}\}

小粉兔的一句话很精辟，虚树是所有关键点形成的极小连通子树。

注意

  1. 虚树的构建需要去重。
  2. 不一定要把虚树建出来。

例题

P3320 [SDOI2015]寻宝游戏

考虑一个可爱的性质,虚树边权和为:

\dfrac{1}{2}\text{dis}(u_i,u_{i+1\bmod |\text{S}|})

这道题就不用建出虚树。

考虑加入一个点 s,按照 dfs 序分类讨论即可。

蓝色是加入的点，红色是要删除的权，绿色是加入的权。