掌握Python虚树算法（从零开始构建高效树形结构处理）

为什么需要虚树？

假设你有一棵包含10⁵个节点的树，每次操作只涉及10个点。如果每次都对整棵树进行DFS或树形DP，时间复杂度会非常高（O(n) 每次操作）。而使用虚树构建技术，我们可以将每次操作的时间复杂度降低到 O(k log k)，其中 k 是关键点数量。

这在处理多组查询、动态规划优化等场景中非常有用，是树形DP优化的重要手段之一。

虚树构建的基本步骤

1. 收集所有关键点。
2. 按 DFS 序（或欧拉序）对关键点排序。
3. 将相邻关键点的 LCA（最近公共祖先）也加入集合。
4. 再次排序去重，得到虚树节点。
5. 用栈模拟 DFS 过程，构建虚树的父子关系。

Python 实现虚树构建

下面是一个完整的 Python 虚树算法实现示例。我们将使用邻接表表示原树，并预处理 LCA 所需的倍增数组。

import syssys.setrecursionlimit(300000)from collections import defaultdictclass VirtualTree:    def __init__(self, n, edges):        self.n = n        self.graph = defaultdict(list)        for u, v in edges:            self.graph[u].append(v)            self.graph[v].append(u)                # 预处理 DFS 序、深度、父节点        self.dfs_order = []        self.depth = [0] * (n + 1)        self.parent = [[0] * 20 for _ in range(n + 1)]        self.in_time = [0] * (n + 1)        self.timer = 0        self._dfs(1, 0)                # 构建倍增表用于 LCA        for j in range(1, 20):            for i in range(1, n + 1):                self.parent[i][j] = self.parent[self.parent[i][j-1]][j-1]        def _dfs(self, u, p):        self.in_time[u] = self.timer        self.dfs_order.append(u)        self.timer += 1        self.parent[u][0] = p        for v in self.graph[u]:            if v != p:                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        # 提升 a 到与 b 同一深度        d = self.depth[a] - self.depth[b]        bit = 0        while d:            if d & 1:                a = self.parent[a][bit]            d //= 2            bit += 1                if a == b:            return a                for j in range(19, -1, -1):            if self.parent[a][j] != self.parent[b][j]:                a = self.parent[a][j]                b = self.parent[b][j]        return self.parent[a][0]        def build_virtual_tree(self, key_nodes):        # 去重并按 DFS 序排序        nodes = sorted(set(key_nodes), key=lambda x: self.in_time[x])                # 添加所有相邻点对的 LCA        m = len(nodes)        for i in range(m - 1):            l = self.lca(nodes[i], nodes[i+1])            nodes.append(l)                # 再次去重并排序        nodes = sorted(set(nodes), key=lambda x: self.in_time[x])                # 用栈构建虚树        stack = [nodes[0]]        virtual_edges = []                for i in range(1, len(nodes)):            u = nodes[i]            while len(stack) > 1 and self.depth[stack[-1]] >= self.depth[u]:                stack.pop()            if stack and self.depth[stack[-1]] < self.depth[u]:                virtual_edges.append((stack[-1], u))                stack.append(u)                return virtual_edges

使用示例

假设我们有一棵如下所示的树（1为根）：

1├── 2│   ├── 4│   └── 5└── 3    └── 6

现在我们要对关键点 [4, 5, 6] 构建虚树：

# 构建原树edges = [(1,2), (1,3), (2,4), (2,5), (3,6)]vt = VirtualTree(6, edges)# 构建虚树key_points = [4, 5, 6]virtual_edges = vt.build_virtual_tree(key_points)print("虚树边:", virtual_edges)# 输出可能为: [(2, 4), (2, 5), (1, 2), (1, 3), (3, 6)]# 实际输出取决于实现细节，但结构正确

应用场景与总结

虚树广泛应用于：算法竞赛技巧如 Codeforces、AtCoder 等平台的高级图论题；处理树上多点距离、最小生成树变种、动态规划状态压缩等问题。

通过本文，你应该已经理解了虚树的核心思想和 Python 实现方法。记住，虚树不是真实存在的树，而是一种树形DP优化的思维工具——它帮助我们在庞大的原树中聚焦于真正重要的部分。

掌握Python虚树算法，将让你在面对复杂树形结构问题时游刃有余！