虚树

发布时间 2023-03-22 21:15:57作者: OIer某罗

第一种定义方式

对于一棵树和若干个给定的点集,如果点集大小之和固定,这个点集的虚树是保留了点集信息的,并且点数和点集大小相关,如下图:
image

注意这里的虚树不包含点 \(11\)\(16\) 中间的 \(13\),因为它并没有起到分叉的作用,如果加上这类点那么点数规模是不对的。

建立虚树

首先取出点集 \(S\),按照 dfn 排序,然后对点集加入每两个数之间的 lca,再按照 dfn 排序(先去重),然后对每两个相邻的点,取其 lca 并连接其与后一个点,如下图:
image

考虑证明:
首先,选出的点集就是最后虚树上的点集。
如果最后一步(取 lca)生成了某一个点:

  1. 如果是原树上两个点的 lca,那么显然在上一步被生成。
  2. 如果是上一步生成的 lca 和另一个点组成,那么这两棵子树上都有点,于是一定会生成该 lca。(区间内每一对相邻点的 lca 等于区间点 lca 等于区间两端点的 lca)

然后考虑选出的点集是否正确。
充分性:
对于虚树上的某一个点,要么其 \(\ge 1\) 个子树上有原点集点,要么其自己是原点集点。对于第一种情况,显然会被两个 dfn 相邻的点生成,对于第二种情况,显然已经选出。
必要性:
选出的点一定都是虚树上的点,显然。

最后考虑加边的正确性:
考虑某点的父亲。其一定是虚树点集内最近的一个祖先。它存在的话,要不自己存在,要不两个子树内都有点。显然这么做就是对的。

第二种定义方式

和第一种不同之处在于加入了点到其在第一种虚树祖先路径上所有的节点,如下所示:
image

它没有点数性质,所以不是拿来维护,可能更普遍的方式是拿来考它的性质之类的。

性质

考虑对原点集 dfn 排序之后为 \(s\),假设原点集\(n\) 个点,那么其点数等于 \(\cfrac{\sum \limits_{i = 1} ^ n dis_{s_i, s_{i + 1}}}{2} + 1\),其中 \(i + 1\) 定义为循环加法,也即 \(i= n\) 的时候是 \(1\),其他时候是正常的 \(i+1\)。这是因为:我们考虑走一遍 \(4 \rightarrow 11 \rightarrow ... \rightarrow 4\) 的路,每条边正好走了一次,然后加上 \(1\) 就是点数。

考虑某一个点集的虚树大小的时候只需要按照 dfn 排序之后两两计算即可。不需要维护虚树。

另一种形式

考虑每一个节点到 \(root\) 的路径并,它就是虚树加上虚树的根到 \(root\) 那一段路。而那一段路也很好求,虚树的根就是所有原点的 lca,这个区间 lca 是好求的。