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

引言

树形结构是计算机科学中最基础的数据组织形式之一，许多实际问题都可以建模为树上的路径或子树查询。当暴力枚举所有路径需要O(n²)时间时，点分治（Centroid Decomposition）提供了一种优雅的分治策略：通过递归地选取树的重心，将问题分解到若干规模不超过原树一半的子树上，从而将复杂度优化到O(n log n)。本文将用Java完整实现点分治框架，并以”统计树上距离不超过K的点对数量”这一经典问题为例，展示算法的完整流程。

树的重心

树的重心是指删除该节点后，最大连通分量的大小最小的节点。关键性质：以重心为根的树，每个子树的大小不超过n/2。

这一性质保证了点分治的递归深度为O(log n)，是复杂度分析的基石。

重心求解算法

1. 任选一个根节点进行DFS，计算每个节点的子树大小
2. 找到使 max(子树大小, n - 子树大小) 最小的节点
3. 该节点即为树的重心

点分治框架

点分治的核心思想是”分而治之”：

1. 分解：找到当前树的重心，以重心为根
2. 统计：统计所有经过重心的合法路径
3. 递归：对每个子树递归执行点分治

路径统计的关键技巧

统计经过重心的路径时，需要避免重复计算完全位于某个子树内部的路径。标准做法是：

1. 先计算以重心为端点的所有路径
2. 对每个子树，先减去该子树内部的路径（容斥原理）
3. 再加上经过重心的跨子树路径

Java完整实现

import java.util.*;

/**
 * 点分治算法实现
 * 以"统计树上距离不超过K的点对数量"为例
 */
public class CentroidDecomposition {

    // 树的边
    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;
    private final int maxDistance;      // 距离上限K

    // 点分治辅助数组
    private boolean[] blocked;          // 标记已被作为重心删除的节点
    private int[] subtreeSize;          // 子树大小
    private int[] distances;            // 收集到的距离数组
    private int distCount;              // 当前收集的距离数量
    private long pairCount;             // 合法点对数量

    @SuppressWarnings("unchecked")
    public CentroidDecomposition(int n, int maxDistance) {
        this.n = n;
        this.maxDistance = maxDistance;
        this.graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        this.blocked = new boolean[n];
        this.subtreeSize = new int[n];
        this.distances = new int[n];
    }

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

    /**
     * 计算子树大小
     */
    private void calcSubtreeSize(int u, int parent) {
        subtreeSize[u] = 1;
        for (Edge e : graph[u]) {
            if (e.to != parent && !blocked[e.to]) {
                calcSubtreeSize(e.to, u);
                subtreeSize[u] += subtreeSize[e.to];
            }
        }
    }

    /**
     * 寻找重心：使最大子树最小的节点
     */
    private int findCentroid(int u, int parent, int totalSize) {
        for (Edge e : graph[u]) {
            if (e.to != parent && !blocked[e.to]) {
                if (subtreeSize[e.to] > totalSize / 2) {
                    return findCentroid(e.to, u, totalSize);
                }
            }
        }
        return u;
    }

    /**
     * 收集从start出发到子树中所有节点的距离
     */
    private void collectDistances(int u, int parent, int dist) {
        if (dist > maxDistance) return;  // 超过上限可提前剪枝
        distances[distCount++] = dist;
        for (Edge e : graph[u]) {
            if (e.to != parent && !blocked[e.to]) {
                collectDistances(e.to, u, dist + e.weight);
            }
        }
    }

    /**
     * 统计数组中距离和不超过maxDistance的点对数量
     * 使用双指针算法，O(m log m)
     */
    private long countPairs(int[] arr, int len) {
        Arrays.sort(arr, 0, len);
        long count = 0;
        int left = 0, right = len - 1;
        while (left < right) {
            if (arr[left] + arr[right] <= maxDistance) {
                count += (right - left);
                left++;
            } else {
                right--;
            }
        }
        return count;
    }

    /**
     * 处理以centroid为重心的子树
     */
    private void processCentroid(int centroid) {
        // 第一步：收集所有以centroid为端点的距离
        distCount = 0;
        distances[distCount++] = 0;  // centroid到自身的距离为0

        // 用于容斥：分别收集每个子树的距离
        List<int[]> childDistArrays = new ArrayList<>();

        for (Edge e : graph[centroid]) {
            if (blocked[e.to]) continue;

            int childStart = distCount;
            collectDistances(e.to, centroid, e.weight);
            int childLen = distCount - childStart;

            // 记录该子树的距离数组，用于后续容斥
            int[] childArr = new int[childLen];
            System.arraycopy(distances, childStart, childArr, 0, childLen);
            childDistArrays.add(childArr);
        }

        // 第二步：计算全局点对（包含所有子树的距离 + centroid自身）
        long totalPairs = countPairs(distances, distCount);

        // 第三步：减去每个子树内部的点对（容斥，避免重复统计不经过centroid的路径）
        long subtractPairs = 0;
        for (int[] childArr : childDistArrays) {
            subtractPairs += countPairs(childArr, childArr.length);
        }

        // 最终经过centroid的合法路径数
        pairCount += (totalPairs - subtractPairs);
    }

    /**
     * 点分治主递归函数
     */
    private void decompose(int entryPoint) {
        // 计算子树大小
        calcSubtreeSize(entryPoint, -1);
        int totalSize = subtreeSize[entryPoint];

        // 找到重心
        int centroid = findCentroid(entryPoint, -1, totalSize);

        // 处理以centroid为重心的路径统计
        processCentroid(centroid);

        // 标记重心为已删除（阻断）
        blocked[centroid] = true;

        // 递归处理每个子树
        for (Edge e : graph[centroid]) {
            if (!blocked[e.to]) {
                decompose(e.to);
            }
        }
    }

    /**
     * 启动点分治，返回距离不超过K的点对数量
     */
    public long solve() {
        pairCount = 0;
        decompose(0);
        return pairCount;
    }

    public static void main(String[] args) {
        // 测试案例：5个节点的树，边权均为1，K=2
        // 结构: 0-1-2-3-4 (链状)
        // 距离<=2的点对有: (0,1),(0,2),(1,2),(1,3),(2,3),(2,4),(3,4) = 7对
        CentroidDecomposition cd = new CentroidDecomposition(5, 2);
        cd.addEdge(0, 1, 1);
        cd.addEdge(1, 2, 1);
        cd.addEdge(2, 3, 1);
        cd.addEdge(3, 4, 1);

        long result = cd.solve();
        System.out.println("距离不超过2的点对数量: " + result);  // 期望: 7

        // 测试案例2：星形树
        // 0为中心，连接1,2,3,4，边权为1，K=2
        // 所有点对距离<=2，共C(5,2)=10对
        CentroidDecomposition cd2 = new CentroidDecomposition(5, 2);
        cd2.addEdge(0, 1, 1);
        cd2.addEdge(0, 2, 1);
        cd2.addEdge(0, 3, 1);
        cd2.addEdge(0, 4, 1);
        System.out.println("星形树距离不超过2的点对数量: " + cd2.solve());  // 期望: 10
    }
}

复杂度分析

应用场景

点分治框架可以解决多种树上路径统计问题：

• 路径长度统计：距离为K的路径数、距离不超过K的路径数
• 路径异或和：路径上权值异或和为特定值的路径数
• 路径最值：路径上的最大/最小边权满足条件的路径数
• 路径染色：树分治配合数据结构（如线段树、树状数组）处理动态问题

与树链剖分的对比

点分治的优势在于无需预处理，适合一次性统计问题；树链剖分适合多次在线查询。

总结

点分治是处理树上路径统计问题的利器，其核心思想——递归分解+容斥统计——具有很高的通用性。掌握点分治后，读者可以尝试解决更复杂的问题，如：

• 边分治：将分解点从节点改为边，某些场景更优
• 动态点分治：配合线段树或树状数组处理带修改的树上查询
• 点分树：将点分治的递归结构显式建为一棵新树，用于在线查询

理解点分治的关键在于把握”重心分解保证复杂度”和”容斥避免重复统计”这两个核心机制。