算法概述
树重心（Tree Centroid）是无向树中一个极其重要的节点：删除该节点后，剩余的所有连通子树中最大的节点数不超过原树节点数的一半。换言之，树重心是使”最大子树最小化”的节点。
树重心不仅是图论中的基础概念，更是点分治（Centroid Decomposition）算法的核心组件。点分治通过递归选取重心将树分解，可将许多 $O(n^2)$ 的树路径统计问题优化到 $O(n \log n)$，在算法竞赛和树形数据处理中具有广泛应用。
核心性质
性质1：存在性与数量
任意一棵树至少有一个、至多有两个重心。若树有两个重心，则它们必定相邻，且删除其中任一个后，另一节点成为剩余子树的重心。
性质2：子树大小约束
设树共有 $n$ 个节点，重心为 $c$。删除 $c$ 后，每棵子树的节点数不超过 $\lfloor n/2 \rfloor$。
性质3：递归分解深度
对一棵树不断选取重心进行分解，分解深度不超过 $O(\log n)$。这是点分治算法复杂度保证的来源。
性质4：路径必经性
树中任意两点间的简单路径必然经过它们的最近公共祖先（LCA）所在的重分解路径上的若干重心。
求树重心的算法
算法思路
通过一次DFS计算每个节点的子树大小（以该节点为根的子树包含的节点数），然后检查每个节点是否满足重心条件：删除该节点后，所有子树（包括”上方子树”，即整棵树减去当前子树）的最大值不超过 $n/2$。
Java完整实现
import java.util.*;
/**
* 树重心（Tree Centroid）算法实现
* 包含：重心查找、重心分解、路径统计应用
*/
public class TreeCentroid {
private final int n;
private final List<Integer>[] adj;
private boolean[] removed;
private int[] subtreeSize;
private int[] parent;
/**
* 构造函数
* @param n 节点数量（0-based编号）
*/
@SuppressWarnings("unchecked")
public TreeCentroid(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.parent = new int[n];
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
adj[u].add(v);
adj[v].add(u);
}
/**
* 计算以root为根的子树大小（不考虑已删除节点）
* @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];
}
}
}
/**
* 在以entry为根的子树中查找重心
* @param entry 子树的入口节点
* @param p 父节点
* @param totalSize 子树总节点数
* @return 重心节点编号
*/
private int findCentroid(int entry, int p, int totalSize) {
for (int v : adj[entry]) {
if (v != p && !removed[v] && subtreeSize[v] > totalSize / 2) {
return findCentroid(v, entry, totalSize);
}
}
return entry;
}
/**
* 查找整棵树的重心
* @return 重心节点编号
*/
public int findCentroid() {
calcSubtreeSize(0, -1);
return findCentroid(0, -1, subtreeSize[0]);
}
/**
* 查找指定节点所在连通块的重心
*/
public int findCentroid(int entry) {
calcSubtreeSize(entry, -1);
return findCentroid(entry, -1, subtreeSize[entry]);
}
/**
* 获取所有重心（1个或2个）
*/
public List<Integer> findAllCentroids() {
List<Integer> centroids = new ArrayList<>();
calcSubtreeSize(0, -1);
int total = subtreeSize[0];
findAllCentroidsDFS(0, -1, total, centroids);
return centroids;
}
private void findAllCentroidsDFS(int u, int p, int total, List<Integer> result) {
boolean isCentroid = true;
int maxPart = total - subtreeSize[u]; // "上方"子树大小
for (int v : adj[u]) {
if (v != p && !removed[v]) {
maxPart = Math.max(maxPart, subtreeSize[v]);
if (subtreeSize[v] > total / 2) {
isCentroid = false;
findAllCentroidsDFS(v, u, total, result);
}
}
}
if (isCentroid && maxPart <= total / 2) {
result.add(u);
}
}
// ==================== 重心分解 ====================
/**
* 重心分解树节点信息
*/
public static class DecompositionNode {
int centroid; // 当前重心
int parentCentroid; // 父重心（根为-1）
int depth; // 分解深度
List<Integer> nodes; // 该层包含的原始节点
DecompositionNode(int centroid, int parent, int depth) {
this.centroid = centroid;
this.parentCentroid = parent;
this.depth = depth;
this.nodes = new ArrayList<>();
}
}
private List<DecompositionNode> decompositionTree;
private int[] centroidParent; // 每个节点在重心分解树中的父重心
private int[] centroidDepth; // 每个节点在重心分解树中的深度
/**
* 执行重心分解
* @return 分解树的层次结构
*/
public List<DecompositionNode> decompose() {
decompositionTree = new ArrayList<>();
centroidParent = new int[n];
centroidDepth = new int[n];
Arrays.fill(centroidParent, -1);
Arrays.fill(centroidDepth, 0);
removed = new boolean[n]; // 重置删除标记
decomposeRecursive(0, -1, 0);
return decompositionTree;
}
/**
* 递归分解子树
* @param entry 子树入口
* @param parentCentroid 父重心
* @param depth 当前分解深度
*/
private void decomposeRecursive(int entry, int parentCentroid, int depth) {
// 计算子树大小
calcSubtreeSize(entry, -1);
int total = subtreeSize[entry];
// 找到重心
int centroid = findCentroid(entry, -1, total);
// 标记删除
removed[centroid] = true;
centroidParent[centroid] = parentCentroid;
centroidDepth[centroid] = depth;
DecompositionNode node = new DecompositionNode(centroid, parentCentroid, depth);
collectNodes(centroid, -1, node.nodes);
decompositionTree.add(node);
// 递归分解每个子连通块
for (int v : adj[centroid]) {
if (!removed[v]) {
decomposeRecursive(v, centroid, depth + 1);
}
}
}
/**
* 收集连通块中的所有节点
*/
private void collectNodes(int u, int p, List<Integer> nodes) {
nodes.add(u);
for (int v : adj[u]) {
if (v != p && !removed[v]) {
collectNodes(v, u, nodes);
}
}
}
// ==================== 应用：统计路径和为K的路径数 ====================
private int pathCountK;
private int targetK;
private int[] nodeValues;
/**
* 统计树中路径和等于K的路径数量（路径可从一个节点到另一个节点）
* 使用重心分解优化到 O(n log n)
*/
public int countPathsWithSum(int[] values, int K) {
this.nodeValues = values;
this.targetK = K;
this.pathCountK = 0;
removed = new boolean[n];
countPathsDecompose(0);
return pathCountK;
}
private void countPathsDecompose(int entry) {
calcSubtreeSize(entry, -1);
int total = subtreeSize[entry];
int centroid = findCentroid(entry, -1, total);
removed[centroid] = true;
// 统计经过重心的路径
Map<Integer, Integer> sumCount = new HashMap<>();
sumCount.put(nodeValues[centroid], 1);
for (int v : adj[centroid]) {
if (removed[v]) continue;
List<Integer> pathSums = new ArrayList<>();
collectPathSums(v, centroid, nodeValues[centroid] + nodeValues[v], pathSums);
// 统计经过重心的路径
for (int sum : pathSums) {
int need = targetK - sum + nodeValues[centroid];
pathCountK += sumCount.getOrDefault(need, 0);
}
// 将当前子树的路径和加入哈希表
for (int sum : pathSums) {
sumCount.merge(sum, 1, Integer::sum);
}
}
// 递归处理子连通块
for (int v : adj[centroid]) {
if (!removed[v]) {
countPathsDecompose(v);
}
}
}
/**
* 收集从start出发到各节点的路径和
*/
private void collectPathSums(int u, int p, int currentSum, List<Integer> sums) {
sums.add(currentSum);
for (int v : adj[u]) {
if (v != p && !removed[v]) {
collectPathSums(v, u, currentSum + nodeValues[v], sums);
}
}
}
// ==================== 工具方法 ====================
/**
* 获取重心分解树中某节点的父重心
*/
public int getCentroidParent(int node) {
return centroidParent[node];
}
/**
* 获取重心分解树中某节点的深度
*/
public int getCentroidDepth(int node) {
return centroidDepth[node];
}
/**
* 打印树的结构
*/
public void printTree() {
System.out.println("Tree structure (adjacency list):");
for (int i = 0; i < n; i++) {
System.out.println(" Node " + i + " -> " + adj[i]);
}
}
/**
* 打印重心分解结果
*/
public void printDecomposition() {
if (decompositionTree == null) {
System.out.println("Please run decompose() first");
return;
}
System.out.println("Centroid Decomposition:");
for (DecompositionNode node : decompositionTree) {
System.out.printf(" Depth %d: centroid=%d, parent=%d, nodes=%s%n",
node.depth, node.centroid, node.parentCentroid, node.nodes);
}
}
public static void main(String[] args) {
// 示例1：基本重心查找
System.out.println("=== Example 1: Basic Centroid ===");
TreeCentroid tc1 = new TreeCentroid(7);
tc1.addEdge(0, 1);
tc1.addEdge(1, 2);
tc1.addEdge(1, 3);
tc1.addEdge(3, 4);
tc1.addEdge(3, 5);
tc1.addEdge(5, 6);
tc1.printTree();
int centroid1 = tc1.findCentroid();
System.out.println("Centroid: " + centroid1);
System.out.println("All centroids: " + tc1.findAllCentroids());
// 示例2：重心分解
System.out.println("\n=== Example 2: Centroid Decomposition ===");
TreeCentroid tc2 = new TreeCentroid(10);
tc2.addEdge(0, 1);
tc2.addEdge(1, 2);
tc2.addEdge(1, 3);
tc2.addEdge(3, 4);
tc2.addEdge(3, 5);
tc2.addEdge(5, 6);
tc2.addEdge(2, 7);
tc2.addEdge(2, 8);
tc2.addEdge(8, 9);
tc2.decompose();
tc2.printDecomposition();
// 示例3：双重心情况
System.out.println("\n=== Example 3: Two Centroids ===");
TreeCentroid tc3 = new TreeCentroid(4);
tc3.addEdge(0, 1);
tc3.addEdge(1, 2);
tc3.addEdge(2, 3); // 路径图 0-1-2-3
System.out.println("All centroids of path graph: " + tc3.findAllCentroids());
// 示例4：路径和统计
System.out.println("\n=== Example 4: Path Sum Count ===");
TreeCentroid tc4 = new TreeCentroid(6);
tc4.addEdge(0, 1);
tc4.addEdge(1, 2);
tc4.addEdge(1, 3);
tc4.addEdge(3, 4);
tc4.addEdge(3, 5);
int[] values = {1, 2, 3, 4, 5, 6};
int K = 7;
int count = tc4.countPathsWithSum(values, K);
System.out.println("Paths with sum " + K + ": " + count);
// 手动验证：1+2+4=7 (0-1-3), 1+2+3=6不对, 3+4=7 (2-1-3), 1+6=7 (0-1-3-5不对)
// 2+5=7 (1-3-4), 1+2+4=7 (0-1-3)
// 示例5：星形树的重心
System.out.println("\n=== Example 5: Star Tree ===");
TreeCentroid tc5 = new TreeCentroid(5);
tc5.addEdge(0, 1);
tc5.addEdge(0, 2);
tc5.addEdge(0, 3);
tc5.addEdge(0, 4);
System.out.println("Star tree centroid: " + tc5.findCentroid());
System.out.println("All centroids: " + tc5.findAllCentroids());
// 示例6：性能测试
System.out.println("\n=== Example 6: Performance Test ===");
int size = 100000;
TreeCentroid tc6 = new TreeCentroid(size);
Random rand = new Random(42);
// 构建随机树
for (int i = 1; i < size; i++) {
tc6.addEdge(i, rand.nextInt(i));
}
long start = System.currentTimeMillis();
int c6 = tc6.findCentroid();
long findTime = System.currentTimeMillis() - start;
System.out.println("Tree size: " + size);
System.out.println("Centroid: " + c6);
System.out.println("Find centroid time: " + findTime + "ms");
start = System.currentTimeMillis();
tc6.decompose();
long decomposeTime = System.currentTimeMillis() - start;
System.out.println("Decompose time: " + decomposeTime + "ms");
System.out.println("Decomposition levels: " + tc6.decompositionTree.size());
// 路径统计性能
int[] largeValues = new int[size];
for (int i = 0; i < size; i++) {
largeValues[i] = rand.nextInt(100) + 1;
}
start = System.currentTimeMillis();
int pathCount = tc6.countPathsWithSum(largeValues, 500);
long pathTime = System.currentTimeMillis() - start;
System.out.println("Path count (K=500): " + pathCount);
System.out.println("Path count time: " + pathTime + "ms");
}
}
关键要点解析
1. 重心条件的等价表述
节点 $u$ 是重心的充要条件是：对于 $u$ 的每个邻接子树 $v$，$size(v) \leq n/2$，且”上方子树”（即 $n – size(u)$）也满足 $\leq n/2$。在DFS中，$size(u)$ 是以 $u$ 为根的子树大小，因此”上方子树”自然为 $n – size(u)$。
2. 重心分解的递归深度保证
每次删除重心后，每棵剩余子树的大小不超过 $n/2$。因此递归深度满足 $T(n) = T(n/2) + O(n)$，由主定理得 $T(n) = O(n \log n)$，分解层数不超过 $\log_2 n$。
3. 路径统计中的容斥原理
在 countPathsWithSum 中，先统计经过重心的所有路径，再递归处理各子树。为避免重复统计完全位于单棵子树内的路径，采用”先统计、后加入”的策略：用哈希表记录已处理子树的路径和，当前子树只与之前子树组合统计，处理完后再将当前子树加入哈希表。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 单次重心查找 | $O(n)$ | $O(n)$ |
| 重心分解 | $O(n \log n)$ | $O(n \log n)$ |
| 路径统计（点分治） | $O(n \log n)$ | $O(n)$ |
应用场景
- 树路径查询：统计满足特定条件（长度、权值和、边数等）的路径数量
- 最近点对变种：树上的距离约束问题
- 动态树维护：结合重心分解处理树的动态修改查询
- 树的中心定位：通信网络中选取最优服务器位置
- 树形DP优化：将 $O(n^2)$ 的树形动态规划优化到 $O(n \log n)$
树重心将”复杂树结构”分解为”对数层级的简单子树”，是连接基础图论与高级算法设计的桥梁。
