每日算法 — 使用java实现重心分解：树形分治与路径统计

引言

在处理树上的路径问题时，暴力枚举所有点对的时间复杂度往往难以接受。重心分解（Centroid Decomposition）是一种将树递归分解为更小子树的分治技术，它通过选取树的重心作为分割点，将树上的问题转化为 log 层子树中的子问题，从而高效求解。本文将用 Java 完整实现重心分解，并演示如何利用它解决路径统计问题。

什么是重心

树的一个节点的重心是指：删除该节点后，剩余的所有连通子树中，最大子树的大小最小。换句话说，重心是让树尽可能”平衡”分割的节点。

重心的性质

• 一棵树最多有两个重心
• 以重心为根的树，每个子树的大小不超过整棵树的一半
• 重心分解的递归深度最多为 O(log n)

算法核心思想

重心分解的过程可以概括为三个步骤：

1. 找重心：在当前子树中找到重心节点
2. 处理跨子树的路径：统计经过当前重心的路径信息
3. 递归分解：对每个连通子树重复上述过程

由于每次选择重心分割，子树规模至少减半，因此递归深度保证为 O(log n)。

Java 完整实现

import java.util.*;

/**
 * 重心分解（Centroid Decomposition）
 * 用于高效处理树上的路径统计问题
 */
public class CentroidDecomposition {
    private int n;                          // 节点数量
    private List<Integer>[] adj;            // 邻接表
    private boolean[] removed;              // 标记节点是否已被作为重心移除
    private int[] subtreeSize;              // 子树大小
    private int[] parentCentroid;           // 每个节点在重心树中的父节点
    private int[] depth;                    // 在重心树中的深度
    private List<List<Integer>> centroidDist; // 每个节点到各层重心的距离

    public CentroidDecomposition(int n) {
        this.n = n;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        this.removed = new boolean[n];
        this.subtreeSize = new int[n];
        this.parentCentroid = new int[n];
        Arrays.fill(parentCentroid, -1);
        this.depth = new int[n];
        this.centroidDist = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            centroidDist.add(new ArrayList<>());
        }
    }

    /**
     * 添加无向边
     */
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }

    /**
     * 计算子树大小（DFS）
     * @param u 当前节点
     * @param p 父节点
     */
    private void calcSubtreeSize(int u, int p) {
        subtreeSize[u] = 1;
        for (int v : adj[u]) {
            if (v != p && !removed[v]) {
                calcSubtreeSize(v, u);
                subtreeSize[u] += subtreeSize[v];
            }
        }
    }

    /**
     * 在当前子树中查找重心
     * @param u 当前节点
     * @param p 父节点
     * @param totalSize 当前子树的总大小
     * @return 重心节点编号
     */
    private int findCentroid(int u, int p, int totalSize) {
        for (int v : adj[u]) {
            if (v != p && !removed[v]) {
                if (subtreeSize[v] > totalSize / 2) {
                    return findCentroid(v, u, totalSize);
                }
            }
        }
        return u;
    }

    /**
     * 收集当前子树中所有节点到根节点的距离
     * @param u 当前节点
     * @param p 父节点
     * @param dist 当前距离
     * @param distances 结果列表
     */
    private void collectDistances(int u, int p, int dist, List<Integer> distances) {
        distances.add(dist);
        for (int v : adj[u]) {
            if (v != p && !removed[v]) {
                collectDistances(v, u, dist + 1, distances);
            }
        }
    }

    /**
     * 统计经过当前重心的路径数量
     * 这里以求距离为K的路径对数为例
     */
    private long countPathsThroughCentroid(int centroid, int K) {
        long count = 0;
        Map<Integer, Integer> freq = new HashMap<>();
        freq.put(0, 1);  // 重心到自身的距离为0

        for (int v : adj[centroid]) {
            if (removed[v]) continue;

            List<Integer> distances = new ArrayList<>();
            collectDistances(v, centroid, 1, distances);

            // 统计经过重心的路径对
            for (int d : distances) {
                if (freq.containsKey(K - d)) {
                    count += freq.get(K - d);
                }
            }

            // 将当前子树的距离加入频率表
            for (int d : distances) {
                freq.put(d, freq.getOrDefault(d, 0) + 1);
            }
        }

        return count;
    }

    /**
     * 重心分解主过程（递归）
     * @param entry 当前子树的入口节点
     * @param parentCent 重心树中的父重心（-1表示根）
     * @param d 当前在重心树中的深度
     */
    public void decompose(int entry, int parentCent, int d) {
        // 1. 计算子树大小
        calcSubtreeSize(entry, -1);

        // 2. 找到重心
        int centroid = findCentroid(entry, -1, subtreeSize[entry]);

        // 3. 标记重心并记录重心树信息
        removed[centroid] = true;
        parentCentroid[centroid] = parentCent;
        depth[centroid] = d;

        // 4. 计算每个节点到当前重心的距离（用于后续查询）
        recordCentroidDistances(centroid, -1, 0, d);

        // 5. 递归处理每个连通子树
        for (int v : adj[centroid]) {
            if (!removed[v]) {
                decompose(v, centroid, d + 1);
            }
        }
    }

    /**
     * 记录每个节点到各层重心的距离
     */
    private void recordCentroidDistances(int u, int p, int dist, int level) {
        // 确保列表有足够长度
        while (centroidDist.get(u).size() <= level) {
            centroidDist.get(u).add(-1);
        }
        centroidDist.get(u).set(level, dist);

        for (int v : adj[u]) {
            if (v != p && !removed[v]) {
                recordCentroidDistances(v, u, dist + 1, level);
            }
        }
    }

    /**
     * 查询节点u到节点v的距离（用于LCA等场景）
     */
    public int queryDistance(int u, int v) {
        int dist = Integer.MAX_VALUE;
        // 遍历u和v在重心树中的公共祖先
        // 简化为：利用重心树的深度和距离信息
        // 实际实现中通常需要维护更完整的结构
        return dist;
    }

    /**
     * 统计树中距离为K的点对数量（主入口）
     */
    public long countKDistancePairs(int K) {
        // 重置状态
        Arrays.fill(removed, false);
        long total = countPathsRecursive(0, K);
        return total;
    }

    private long countPathsRecursive(int entry, int K) {
        calcSubtreeSize(entry, -1);
        int centroid = findCentroid(entry, -1, subtreeSize[entry]);
        removed[centroid] = true;

        long count = countPathsThroughCentroid(centroid, K);

        for (int v : adj[centroid]) {
            if (!removed[v]) {
                count += countPathsRecursive(v, K);
            }
        }

        return count;
    }

    public static void main(String[] args) {
        // 示例：统计距离为2的点对数量
        int n = 6;
        CentroidDecomposition cd = new CentroidDecomposition(n);

        // 构建一棵树：0-1, 0-2, 1-3, 1-4, 4-5
        cd.addEdge(0, 1);
        cd.addEdge(0, 2);
        cd.addEdge(1, 3);
        cd.addEdge(1, 4);
        cd.addEdge(4, 5);

        // 执行重心分解
        cd.decompose(0, -1, 0);

        System.out.println("Centroid decomposition completed.");

        // 统计距离为2的路径对
        Arrays.fill(cd.removed, false);
        long pairs = cd.countKDistancePairs(2);
        System.out.println("Pairs with distance 2: " + pairs);
    }
}

算法复杂度分析

由于每次选择重心都会使子树规模至少减半，递归深度为 O(log n)，因此整体时间复杂度为 O(n log n)。

应用场景

重心分解广泛应用于以下场景：

• 树上路径统计：统计满足特定条件的路径数量（如距离为K的路径对）
• 最近点查询：维护动态点集，查询距离某点最近的点
• 动态树问题：结合数据结构实现子树修改与路径查询
• 树分治优化DP：在树上进行分治优化的动态规划

总结

重心分解是解决树上路径问题的利器。通过递归选取重心将树分割，我们将一个复杂的树形问题分解为多个独立的子问题，每层仅处理 O(n) 规模的数据，利用对数层的递归深度达到高效的 O(n log n) 复杂度。掌握重心分解，将帮助你优雅地解决大量树上的统计与查询问题。