虚树

What · 是什么

虚树（Virtual Tree）是对树的「关键点集」做的一种压缩表示：给定 k 个关键点，只保留它们两两的 LCA 作为辅助节点，再加上各 LCA 之间的祖先关系，形成一棵只含 O(k) 个节点的小树。由于原树中绝大多数节点对某次询问没有影响，虚树把「每次 O(n) 的树 DP」变成「O(k log k) 建树 + O(k) DP」，当多次询问且 Σ关键点远小于 n×q 时收益巨大。虚树中保留的边权是原树上的路径权（距离或路径最小值等），祖先关系与原来一致。

Why · 为什么

How · 实现

伪代码

build_vtree(keys):
  k = keys 按 dfn 排序
  st = [1]                    # 栈内维护当前链，默认根节点1加入
  for x in k:
    if x == st[-1]: continue
    l = lca(x, st[-1])
    if l != st[-1]:
      while len(st) > 1 and dfn[st[-2]] >= dfn[l]:
        add_edge(st[-2], st[-1]); st.pop()
      if st[-1] != l:
        add_edge(l, st[-1]); st.pop(); st.append(l)
    st.append(x)
  while len(st) > 1:
    add_edge(st[-2], st[-1]); st.pop()

Python 实现

import sys

sys.setrecursionlimit(1 << 20)


class LCA:
    def __init__(self, n, G):
        self.n = n
        self.G = G
        self.depth = [0] * (n + 1)
        self.up = [[0] * (n + 1) for _ in range(17)]
        self.dfn = [0] * (n + 1)
        self.timer = 0
        self._dfs(1, 0)

    def _dfs(self, u, f):
        self.timer += 1
        self.dfn[u] = self.timer
        self.up[0][u] = f
        for i in range(1, 17):
            self.up[i][u] = self.up[i - 1][self.up[i - 1][u]]
        for v in self.G[u]:
            if v != f:
                self.depth[v] = self.depth[u] + 1
                self._dfs(v, u)

    def lca(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a
        diff = self.depth[a] - self.depth[b]
        i = 0
        while diff:
            if diff & 1:
                a = self.up[i][a]
            diff >>= 1
            i += 1
        if a == b:
            return a
        for i in range(16, -1, -1):
            if self.up[i][a] != self.up[i][b]:
                a = self.up[i][a]
                b = self.up[i][b]
        return self.up[0][a]


def build_vtree(n, G, lca_inst, keys):
    ks = sorted(keys, key=lambda x: lca_inst.dfn[x])
    st = [1]
    vt = {}
    for x in ks:
        if x == st[-1]:
            continue
        l = lca_inst.lca(x, st[-1])
        if l != st[-1]:
            while len(st) > 1 and lca_inst.dfn[st[-2]] >= lca_inst.dfn[l]:
                vt.setdefault(st[-2], []).append(st[-1])
                st.pop()
            if st[-1] != l:
                vt.setdefault(l, []).append(st[-1])
                st.pop()
                st.append(l)
        st.append(x)
    while len(st) > 1:
        vt.setdefault(st[-2], []).append(st[-1])
        st.pop()
    return vt


def main():
    n = 8
    edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (5, 8)]
    G = [[] for _ in range(n + 1)]
    for a, b in edges:
        G[a].append(b)
        G[b].append(a)
    lca_inst = LCA(n, G)
    vt = build_vtree(n, G, lca_inst, [4, 6, 7, 8])
    print("virtual tree edges:")
    for u, vs in sorted(vt.items()):
        for v in vs:
            print(f"  {u} -> {v}")
    # 手算：关键点 {4,6,7,8}；LCA(4,8)=2, LCA(6,7)=3, LCA(2,3)=1, LCA(7,8)=1
    # 虚树节点 {1,2,3,4,6,7,8}；边 2->4, 2->8, 3->6, 3->7, 1->2, 1->3
    expect = {(2, 4), (2, 8), (3, 6), (3, 7), (1, 2), (1, 3)}
    got = set()
    for u, vs in vt.items():
        for v in vs:
            got.add((u, v))
    assert got == expect, got
    print("OK")


if __name__ == "__main__":
    main()

易错点

• 相邻关键点求 LCA 而不是全部两两求（两两是 O(k^2) 会 TLE）
• 排序/去重必须按 dfn，否则建出的父子关系错乱
• 单调栈弹栈连边时，若 lca 不在栈中要先入栈（否则丢掉分岔点）
• 重复关键点去重（同一 LCA 可能被多次加入）
• 边权 = 原树距离，别用 dfn 差；路径最小值需倍增预处理 min-up
• DP 时遍历虚树子树要用虚树邻接表，不能递归到原树非虚树节点

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/virtual-tree/
• oiwiki_raw✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/virtual-tree.md