xxx 树的重心（Centroid of a Tree）问题

字数 2810 2025-12-14 06:22:41

好的，让我们来学习一个新的图论算法题目。

xxx 树的重心（Centroid of a Tree）问题

题目描述

给定一棵有 n 个节点的无向树（连通无环图）。树的重心定义为一个节点，当从树中删除该节点后，剩下的各个连通分量（即各个子树）中，包含节点数最多的那个分量的节点数最小。

更形式化地说，对于树中的任意节点 u，定义 maxSubtreeSize(u) 为：将 u 从树中移除后，形成的所有连通块中，节点数量的最大值。那么，树的重心是使得 maxSubtreeSize(u) 最小的那个（或那些）节点 u。

关键性质：

一棵树最多有两个重心，且如果存在两个重心，它们一定是相邻的。
重心可以将树的“平衡性”最大化，这使得它在许多树形问题（如树分治算法）中是关键的支点。

我们的任务是：找到一棵给定树的所有重心。

输入：

树的节点数 n（编号通常为 1 到 n）。
接下来的 n-1 行，每行两个整数 u 和 v，表示树中有一条连接 u 和 v 的边。

输出：

树的所有重心的编号。

解题过程循序渐进讲解

步骤 1：理解问题与观察

想象一棵树，我们任意选择一个节点 u 作为“假想”的重心。

当我们移除 u 时，树会被分成几部分？
1. u 的每个子节点 v 所在的子树。
2. u 的“父节点”方向（如果我们把 u 当作根来看）的那个连通块。
我们需要快速计算这些部分的大小。

这提示我们，需要一个能计算每个节点子树大小的预处理步骤。由于树是无向的，我们需要先指定一个根（比如节点1），将无向树转换为有根树。

步骤 2：核心思路与定义

我们进行一次深度优先搜索（DFS），计算出以每个节点为根的子树大小 subtreeSize[u]。

对于任意一个节点 u，在将其视为重心时，各部分的大小为：

对于 u 的每一个子节点 v，其所在部分的大小就是 subtreeSize[v]。
对于 u 的父节点方向的部分，其大小为 n - subtreeSize[u]。

因此，maxSubtreeSize(u) = max( n - subtreeSize[u], max_{v是u的子节点}(subtreeSize[v]) )。

我们的目标就是找到令 maxSubtreeSize(u) 最小的节点 u。

步骤 3：算法流程详解

构建邻接表：根据输入构建树的邻接表表示。
第一次 DFS（后序遍历）：
- 任选一个根节点（例如1），进行DFS。
- DFS函数 dfs(u, parent) 返回以 u 为根的子树大小。
- 在递归过程中，累加所有子节点 v（v != parent）的子树大小，得到 subtreeSize[u]。
- 同时，在这个节点 u 处，我们其实已经可以知道它作为重心时，其子节点方向的最大子树大小 maxChildSize。
实时计算与更新：
- 在计算节点 u 的 subtreeSize 时，对于每个子节点 v，我们得到了 sizeV = subtreeSize[v]。用这个值更新 u 的 maxChildSize。
- 当 u 的所有子节点处理完后，我们就能算出 u 的 maxSubtreeSize(u) = max(maxChildSize, n - subtreeSize[u])。
- 维护一个全局变量 minMaxSize 记录当前找到的最小 maxSubtreeSize。
- 维护一个列表 centroids 来存储所有使得 maxSubtreeSize(u) 等于 minMaxSize 的节点 u。
第二次遍历（可选但高效）：
- 实际上，我们可以在第一次DFS中就完成所有计算！当递归返回到节点 u 时，我们已经知道了 subtreeSize[u] 和它的 maxChildSize，因此可以立即计算 maxSubtreeSize(u) 并与全局最优解比较。
- 这样只需要一次DFS，时间复杂度是 O(n)。

步骤 4：示例演示

假设有一棵7个节点的树，边为：(1,2), (1,3), (2,4), (2,5), (3,6), (3,7)。这是一棵以1为根的“星形”树，但节点2和3各有两个孩子。

让我们以节点2为例进行计算：

假设根是1。
subtreeSize[2] = 3（节点2，4，5）。
节点2的子节点是4和5，它们的子树大小都是1。所以 maxChildSize = 1。
父节点方向部分的大小是 n - subtreeSize[2] = 7 - 3 = 4。
所以 maxSubtreeSize(2) = max(1, 4) = 4。

现在计算真正的重心：

通过一次DFS，我们会发现节点1的 maxSubtreeSize 是4（其子节点2和3的子树大小都是3）。
节点2和节点3的 maxSubtreeSize 是4（如上计算）。
节点4、5、6、7是叶子节点，它们的 maxSubtreeSize 是6（因为移除叶子后，剩下的大连通块有6个节点）。
因此，minMaxSize = 4，重心是节点1。实际上这棵树只有一个重心。

如果树是一条链 1-2-3-4-5（n=5）：

节点3的 maxSubtreeSize 是 max(2, 2) = 2（移除3后，得到两个大小都为2的部分）。
节点2的 maxSubtreeSize 是 max(1, 4) = 4。
节点4同理。
节点1和5是 max(1, 4)=4。
所以重心是节点3。对于偶数节点的链（如1-2-3-4），节点2和3的 maxSubtreeSize 都是2，此时会有两个重心。

步骤 5：算法实现要点

使用递归或栈进行DFS。
subtreeSize 数组初始化为1（节点自身）。
在递归返回前，更新当前节点 u 的 maxSubtreeSize 并与全局最优比较。
由于最多有两个重心，centroids 列表大小不会超过2。

步骤 6：复杂度分析

时间复杂度：O(n)，我们只对树进行了一次深度优先遍历，每个节点和每条边都被访问常数次。
空间复杂度：O(n)，用于存储邻接表、子树大小数组以及递归栈（在最坏链的情况下深度为O(n)）。

步骤 7：总结

树的重心问题通过一次巧妙的DFS同时计算子树大小和评估节点的“平衡性”来解决。其核心在于理解 maxSubtreeSize(u) 的构成，并利用DFS后序遍历的特性，在获得子节点信息后立即完成对当前节点的计算。这个算法是更高级算法（如树的分治）的基础构件。

好的，让我们来学习一个新的图论算法题目。 xxx 树的重心（Centroid of a Tree）问题题目描述给定一棵有 n 个节点的无向树（连通无环图）。树的重心定义为一个节点，当从树中删除该节点后，剩下的各个连通分量（即各个子树）中，包含节点数最多的那个分量的节点数最小。更形式化地说，对于树中的任意节点 u ，定义 maxSubtreeSize(u) 为：将 u 从树中移除后，形成的所有连通块中，节点数量的最大值。那么，树的重心是使得 maxSubtreeSize(u) 最小的那个（或那些）节点 u 。关键性质：一棵树最多有两个重心，且如果存在两个重心，它们一定是相邻的。重心可以将树的“平衡性”最大化，这使得它在许多树形问题（如树分治算法）中是关键的支点。我们的任务是：找到一棵给定树的所有重心。输入：树的节点数 n （编号通常为 1 到 n）。接下来的 n-1 行，每行两个整数 u 和 v ，表示树中有一条连接 u 和 v 的边。输出：树的所有重心的编号。解题过程循序渐进讲解步骤 1：理解问题与观察想象一棵树，我们任意选择一个节点 u 作为“假想”的重心。当我们移除 u 时，树会被分成几部分？ u 的每个子节点 v 所在的子树。 u 的“父节点”方向（如果我们把 u 当作根来看）的那个连通块。我们需要快速计算这些部分的大小。这提示我们，需要一个能计算每个节点子树大小的预处理步骤。由于树是无向的，我们需要先指定一个根（比如节点1），将无向树转换为有根树。步骤 2：核心思路与定义我们进行一次深度优先搜索（DFS），计算出以每个节点为根的子树大小 subtreeSize[u] 。对于任意一个节点 u ，在将其视为重心时，各部分的大小为：对于 u 的每一个子节点 v ，其所在部分的大小就是 subtreeSize[v] 。对于 u 的父节点方向的部分，其大小为 n - subtreeSize[u] 。因此， maxSubtreeSize(u) = max( n - subtreeSize[u], max_{v是u的子节点}(subtreeSize[v]) ) 。我们的目标就是找到令 maxSubtreeSize(u) 最小的节点 u 。步骤 3：算法流程详解构建邻接表：根据输入构建树的邻接表表示。第一次 DFS（后序遍历）：任选一个根节点（例如1），进行DFS。 DFS函数 dfs(u, parent) 返回以 u 为根的子树大小。在递归过程中，累加所有子节点 v （ v != parent ）的子树大小，得到 subtreeSize[u] 。同时，在这个节点 u 处，我们其实已经可以知道它作为重心时，其子节点方向的最大子树大小 maxChildSize 。实时计算与更新：在计算节点 u 的 subtreeSize 时，对于每个子节点 v ，我们得到了 sizeV = subtreeSize[v] 。用这个值更新 u 的 maxChildSize 。当 u 的所有子节点处理完后，我们就能算出 u 的 maxSubtreeSize(u) = max(maxChildSize, n - subtreeSize[u]) 。维护一个全局变量 minMaxSize 记录当前找到的最小 maxSubtreeSize 。维护一个列表 centroids 来存储所有使得 maxSubtreeSize(u) 等于 minMaxSize 的节点 u 。第二次遍历（可选但高效）：实际上，我们可以在第一次DFS中就完成所有计算！当递归返回到节点 u 时，我们已经知道了 subtreeSize[u] 和它的 maxChildSize ，因此可以立即计算 maxSubtreeSize(u) 并与全局最优解比较。这样只需要一次DFS，时间复杂度是 O(n)。步骤 4：示例演示假设有一棵7个节点的树，边为： (1,2), (1,3), (2,4), (2,5), (3,6), (3,7) 。这是一棵以1为根的“星形”树，但节点2和3各有两个孩子。让我们以节点2为例进行计算：假设根是1。 subtreeSize[2] = 3 （节点2，4，5）。节点2的子节点是4和5，它们的子树大小都是1。所以 maxChildSize = 1 。父节点方向部分的大小是 n - subtreeSize[2] = 7 - 3 = 4 。所以 maxSubtreeSize(2) = max(1, 4) = 4 。现在计算真正的重心：通过一次DFS，我们会发现节点1的 maxSubtreeSize 是4（其子节点2和3的子树大小都是3）。节点2和节点3的 maxSubtreeSize 是4（如上计算）。节点4、5、6、7是叶子节点，它们的 maxSubtreeSize 是6（因为移除叶子后，剩下的大连通块有6个节点）。因此， minMaxSize = 4 ，重心是节点1。实际上这棵树只有一个重心。如果树是一条链 1-2-3-4-5 （n=5）：节点3的 maxSubtreeSize 是 max(2, 2) = 2 （移除3后，得到两个大小都为2的部分）。节点2的 maxSubtreeSize 是 max(1, 4) = 4 。节点4同理。节点1和5是 max(1, 4)=4 。所以重心是节点3。对于偶数节点的链（如1-2-3-4），节点2和3的 maxSubtreeSize 都是2，此时会有两个重心。步骤 5：算法实现要点使用递归或栈进行DFS。 subtreeSize 数组初始化为1（节点自身）。在递归返回前，更新当前节点 u 的 maxSubtreeSize 并与全局最优比较。由于最多有两个重心， centroids 列表大小不会超过2。步骤 6：复杂度分析时间复杂度：O(n)，我们只对树进行了一次深度优先遍历，每个节点和每条边都被访问常数次。空间复杂度：O(n)，用于存储邻接表、子树大小数组以及递归栈（在最坏链的情况下深度为O(n)）。步骤 7：总结树的重心问题通过一次巧妙的DFS同时计算子树大小和评估节点的“平衡性”来解决。其核心在于理解 maxSubtreeSize(u) 的构成，并利用DFS后序遍历的特性，在获得子节点信息后立即完成对当前节点的计算。这个算法是更高级算法（如树的分治）的基础构件。