虚树(Virtual Tree)

虚树(Virtual Tree),又称关键点树,是一种用于加速树上多询问问题的辅助结构。当每组询问只关注原树中的一部分关键节点时,虚树把这些关键点以及它们之间必要的最近公共祖先压缩成一棵小树,保留原有的祖先关系,从而避免每次都在整棵大树上计算。

概述

某些问题给出一棵固定的大树,并有多组询问,每组指定若干关键点,要求在这些点构成的结构上做动态规划或统计。若询问总点数不大,但直接在原树上处理会因树大而超时。虚树的思想是:只有关键点和它们两两的最近公共祖先才对结果有影响,其余节点可以忽略或压缩成边,构造出的虚树节点数是关键点数的常数倍。

核心原理

• 按深度优先遍历的时间戳(DFS 序)对关键点排序,保证构建时祖先关系正确。
• 依次将关键点入栈,利用最近公共祖先判断当前点与栈顶的关系,在必要处插入两点的最近公共祖先作为虚树节点。
• 用单调栈维护当前虚树的最右链,弹栈时连边,最终得到一棵包含所有关键点及其关键祖先的树。
• 虚树的节点数不超过关键点数的两倍,单次构建复杂度约为 O(k log k),k 为关键点数。

应用场景

虚树常用于多次给定关键点集合、要求在其上做树形动态规划的问题,例如统计关键点间的最小割边权和、关键点到根路径的交集、树上覆盖与染色等。它把总复杂度从与树规模相关转化为与关键点总量相关。

常见问题

问:为什么虚树节点数只有关键点的常数倍?答:每插入一个关键点最多新增一个作为最近公共祖先的辅助节点,因此总节点数不超过关键点数的两倍。

问:构建虚树前为什么要按 DFS 序排序?答:DFS 序能保证节点按照进入子树的先后排列,配合单调栈可正确恢复祖先后代关系,避免连错边。