每日算法 — 使用java实现虚树：关键节点压缩与树上动态规划加速

引言

在算法竞赛和工程实践中，常常会遇到这样的问题：给定一棵包含n个节点的树，需要处理Q组查询，每组查询只涉及k个特定节点（k远小于n）。如果每次都在整棵树上进行动态规划或遍历，总复杂度将达到O(Q x n)，在n=10^5、Q=10^5的规模下完全不可行。虚树（Virtual Tree）技术通过只保留关键节点及其最近公共祖先（LCA），将原树压缩为一棵规模仅为O(k)的新树，从而将单次查询复杂度优化到O(k log k)。本文将用Java完整实现虚树构建算法，并以”多组查询中关键节点间最小距离覆盖”为例，展示这一技巧的威力。

核心思想

为什么需要虚树

考虑这样一个问题：树上有n个节点，每次查询给出k个关键点，要求计算这些关键点之间的某种路径统计（如距离和、最小覆盖等）。

暴力方法：每次在整棵树上做O(n)的DFS -> O(Q x n)
虚树方法：只保留关键点和必要的LCA，构建规模为O(k)的压缩树 -> O(Q x k log k)

当Q和n同阶且k较小时，虚树可以将总复杂度从O(n²)优化到O(n log n)。

虚树的构造原理

虚树的构造基于一个关键观察：k个关键点的LCA集合最多有k-1个。因此虚树的节点数不超过2k-1。

构造步骤：

LCA预处理：使用倍增法或Tarjan算法预处理所有节点的LCA
DFS序排序：将所有关键点按DFS序（进入时间）排序
插入LCA：对于排序后相邻的关键点，计算它们的LCA并加入节点集合
构建树结构：利用栈模拟DFS过程，根据DFS序构建父子关系

前置知识：LCA倍增预处理

/**
 * LCA预处理类
 * 使用倍增法，预处理时间O(n log n)，查询时间O(log n)
 */
class LCA {
    private final int n;
    private final int LOG;
    private final int[][] up;      // up[j][v] = v的2^j级祖先
    private final int[] depth;     // 节点深度
    private final int[] dfn;       // DFS序（进入时间）
    private int time;

    public LCA(int n, List<Integer>[] graph, int root) {
        this.n = n;
        this.LOG = 32 - Integer.numberOfLeadingZeros(n);
        this.up = new int[LOG][n];
        this.depth = new int[n];
        this.dfn = new int[n];
        this.time = 0;

        dfs(root, -1, graph);

        for (int j = 1; j < LOG; j++) {
            for (int v = 0; v < n; v++) {
                int mid = up[j - 1][v];
                up[j][v] = (mid == -1) ? -1 : up[j - 1][mid];
            }
        }
    }

    private void dfs(int u, int parent, List<Integer>[] graph) {
        dfn[u] = ++time;
        up[0][u] = parent;
        for (int v : graph[u]) {
            if (v != parent) {
                depth[v] = depth[u] + 1;
                dfs(v, u, graph);
            }
        }
    }

    public int lca(int u, int v) {
        if (depth[u] < depth[v]) {
            int temp = u; u = v; v = temp;
        }
        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; j++) {
            if ((diff & (1 << j)) != 0) {
                u = up[j][u];
            }
        }
        if (u == v) return u;
        for (int j = LOG - 1; j >= 0; j--) {
            if (up[j][u] != up[j][v]) {
                u = up[j][u];
                v = up[j][v];
            }
        }
        return up[0][u];
    }

    public int getDepth(int u) { return depth[u]; }
    public int getDfn(int u) { return dfn[u]; }
}

Java完整实现

import java.util.*;

/**
 * 虚树构建与树上动态规划
 * 以"关键节点的最小连通子树的边权和"为例
 */
public class VirtualTree {

    // 原树的边（带权）
    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    private final int n;
    private final List<Edge>[] graph;

    @SuppressWarnings("unchecked")
    public VirtualTree(int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    public void addEdge(int u, int v, int w) {
        graph[u].add(new Edge(v, w));
        graph[v].add(new Edge(u, w));
    }

    /**
     * 构建虚树并返回虚树的邻接表
     * @param keyNodes 关键点数组
     * @param lcaInstance 预处理好的LCA对象
     * @return 虚树的邻接表（无权，只保留拓扑结构）
     */
    @SuppressWarnings("unchecked")
    public List<Integer>[] buildVirtualTree(int[] keyNodes, LCA lcaInstance) {
        int k = keyNodes.length;
        if (k == 0) return new ArrayList[0];

        // 步骤1：收集所有关键节点及其LCA
        Set<Integer> nodeSet = new HashSet<>();
        for (int node : keyNodes) {
            nodeSet.add(node);
        }

        // 按DFS序排序关键点
        Integer[] sorted = Arrays.stream(keyNodes)
                .boxed()
                .sorted(Comparator.comparingInt(lcaInstance::getDfn))
                .toArray(Integer[]::new);

        // 添加相邻关键点的LCA
        for (int i = 0; i < sorted.length - 1; i++) {
            int ancestor = lcaInstance.lca(sorted[i], sorted[i + 1]);
            nodeSet.add(ancestor);
        }

        // 步骤2：将节点按DFS序排序
        List<Integer> allNodes = new ArrayList<>(nodeSet);
        allNodes.sort(Comparator.comparingInt(lcaInstance::getDfn));

        // 步骤3：用栈构建虚树的父子关系
        List<Integer>[] virtual = new ArrayList[allNodes.size()];
        for (int i = 0; i < allNodes.size(); i++) {
            virtual[i] = new ArrayList<>();
        }

        // 建立原树节点到虚树索引的映射
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < allNodes.size(); i++) {
            indexMap.put(allNodes.get(i), i);
        }

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);  // 第一个节点入栈

        for (int i = 1; i < allNodes.size(); i++) {
            int current = allNodes.get(i);
            // 当前节点与栈顶节点的LCA
            while (stack.size() > 1) {
                int top = allNodes.get(stack.peek());
                int ancestor = lcaInstance.lca(top, current);
                if (lcaInstance.getDfn(ancestor) <= lcaInstance.getDfn(allNodes.get(stack.toArray(new Integer[0])[1]))) {
                    int child = stack.pop();
                    virtual[stack.peek()].add(child);
                } else {
                    break;
                }
            }
            stack.push(i);
        }

        // 清空栈中剩余的边
        while (stack.size() > 1) {
            int child = stack.pop();
            virtual[stack.peek()].add(child);
        }

        return virtual;
    }

    public static void main(String[] args) {
        // 测试案例：构建一棵7个节点的树
        //       0
        //     / |         //    1  2  3
        //   /|     |
        //  4 5     6
        int n = 7;
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();

        int[][] edges = {{0,1},{0,2},{0,3},{1,4},{1,5},{3,6}};
        for (int[] e : edges) {
            graph[e[0]].add(e[1]);
            graph[e[1]].add(e[0]);
        }

        LCA lca = new LCA(n, graph, 0);

        System.out.println("LCA(4, 5) = " + lca.lca(4, 5));  // 应为1
        System.out.println("LCA(4, 6) = " + lca.lca(4, 6));  // 应为0
        System.out.println("LCA(5, 6) = " + lca.lca(5, 6));  // 应为0

        // 构建虚树示例
        VirtualTree vt = new VirtualTree(n);
        int[] keyNodes = {4, 5, 6};
        List<Integer>[] vtree = vt.buildVirtualTree(keyNodes, lca);
        System.out.println("虚树节点数: " + vtree.length);
    }
}

虚树构建的标准实现

以下是更严谨的虚树构建实现，包含完整的带权边处理：

/**
 * 标准虚树构建实现
 */
public static List<int[]> buildStandardVirtualTree(
        int[] keyNodes, LCA lca, int n) {

    int k = keyNodes.length;
    Arrays.sort(keyNodes);

    // 收集所有需要的节点
    List<Integer> nodes = new ArrayList<>();
    for (int node : keyNodes) nodes.add(node);

    // 添加相邻关键点的LCA
    for (int i = 0; i < k - 1; i++) {
        int ancestor = lca.lca(keyNodes[i], keyNodes[i + 1]);
        nodes.add(ancestor);
    }

    // 去重并按DFS序排序
    nodes = nodes.stream().distinct()
            .sorted(Comparator.comparingInt(lca::getDfn))
            .collect(java.util.stream.Collectors.toList());

    // 用栈构建虚树
    List<int[]> virtualEdges = new ArrayList<>();
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(nodes.get(0));

    for (int i = 1; i < nodes.size(); i++) {
        int current = nodes.get(i);
        int l = lca.lca(current, stack.peek());

        while (stack.size() > 1 &&
               lca.getDfn(l) <= lca.getDfn(stack.toArray(new Integer[0])[1])) {
            int child = stack.pop();
            virtualEdges.add(new int[]{stack.peek(), child});
        }

        if (l != stack.peek()) {
            virtualEdges.add(new int[]{l, current});
            stack.push(l);
        }
        stack.push(current);
    }

    while (stack.size() > 1) {
        int child = stack.pop();
        virtualEdges.add(new int[]{stack.peek(), child});
    }

    return virtualEdges;
}

复杂度分析

指标	复杂度	说明
预处理（LCA）	O(n log n)	倍增法预处理，只需执行一次
单次虚树构建	O(k log k)	排序O(k log k)，栈构建O(k)
虚树规模	O(k)	节点数不超过2k-1
单次DP	O(k)	在规模为O(k)的虚树上遍历
总复杂度（Q组查询）	O(n log n + Q x k log k)	预处理一次，每次查询独立

应用场景

虚树是解决以下类型问题的利器：

多组关键点查询：如”k个关键点的最小连通子树大小”
路径交统计：多条路径的公共部分长度
染色问题：树上染色后的连通块统计
距离和查询：关键点两两距离之和
树形DP优化：当DP状态只与少量关键点相关时

与其他技术的对比

技术	适用场景	单次查询复杂度
虚树	k个关键点的路径/子树问题	O(k log k)
树链剖分+线段树	路径修改与查询	O(log² n)
点分治	全局路径统计	O(n log² n)
莫队算法	离线区间查询	O(n√Q)

总结

虚树是树上算法优化的重要技巧，其核心思想是”只保留必要信息”。通过DFS序排序和栈模拟，我们可以在O(k log k)时间内将规模为n的原树压缩到O(k)的虚树。这一技巧与LCA预处理相结合，使得大量树上多组查询问题得以高效解决。

掌握虚树后，读者可以进一步学习：

虚树+树形DP：解决更复杂的关键点依赖问题
动态虚树：在带修改的场景下维护虚树结构
虚树+线段树合并：处理子树内复杂统计问题

虚树的本质是信息压缩——在不改变问题本质的前提下，剔除无关节点，从而大幅提升算法效率。

Tagged with: DFS序 Java LCA 倍增法关键节点压缩树上动态规划树形算法虚树