用C++搞定树的重心与直径：从LeetCode刷题到解决「医院选址」实际问题
树结构在算法竞赛和实际应用中无处不在，从社交网络的关系图谱到城市交通的路网规划，理解树的特性往往能帮助我们高效解决问题。本文将深入探讨树的两个核心概念——重心与直径，并展示如何用C++实现相关算法，最终解决类似「医院选址」的实际问题。
1. 树的重心：概念与算法实现
树的重心是树中一个特殊的节点，删除该节点后，剩余子树的最大节点数最小。这个概念在优化问题中非常有用，比如在网络布局中寻找关键节点。
1.1 重心的数学定义与性质
树的重心有以下重要性质：
- 一棵树最多有两个重心，且它们相邻
- 以重心为根时，所有子树的大小不超过整棵树的一半
- 树中所有点到重心的距离和最小
这些性质使得重心成为许多优化问题的理想选择点，比如我们后面会讨论的医院选址问题。
1.2 寻找重心的DFS算法
我们可以通过一次DFS遍历找到树的重心。关键思路是：对于每个节点，计算删除它后最大子树的节点数，然后选择使这个值最小的节点。
#include <iostream> #include <vector> using namespace std; const int N = 1e5 + 10; vector<int> tree[N]; int size[N], max_part[N]; int n, centroid = 0, min_max_part = INT_MAX; void dfs(int u, int parent) { size[u] = 1; max_part[u] = 0; for (int v : tree[u]) { if (v == parent) continue; dfs(v, u); size[u] += size[v]; max_part[u] = max(max_part[u], size[v]); } max_part[u] = max(max_part[u], n - size[u]); if (max_part[u] < min_max_part || (max_part[u] == min_max_part && u < centroid)) { min_max_part = max_part[u]; centroid = u; } } int main() { cin >> n; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; tree[u].push_back(v); tree[v].push_back(u); } dfs(1, -1); cout << "Centroid: " << centroid << ", Max part size: " << min_max_part << endl; return 0; }提示：在实际应用中，如果树有两个重心，上述代码会选择编号较小的那个。可以根据需要修改选择逻辑。
2. 树的直径：两种高效计算方法
树的直径是指树中任意两点间最长路径的长度。计算直径有两种经典方法：两次DFS/BFS和树形DP。
2.1 两次DFS/BFS方法
这种方法基于一个关键性质：从任意节点出发的最远点一定是直径的一个端点。
#include <iostream> #include <vector> #include <queue> using namespace std; pair<int, int> findFarthest(const vector<vector<int>>& tree, int start) { vector<int> dist(tree.size(), -1); queue<int> q; q.push(start); dist[start] = 0; int farthest = start, max_dist = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : tree[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); if (dist[v] > max_dist) { max_dist = dist[v]; farthest = v; } } } } return {farthest, max_dist}; } int treeDiameter(const vector<vector<int>>& tree) { if (tree.empty()) return 0; int u = findFarthest(tree, 0).first; return findFarthest(tree, u).second; }2.2 树形DP方法
这种方法可以处理带权树（包括负权边）的情况，更具通用性。
#include <iostream> #include <vector> using namespace std; int diameter = 0; int dfsDP(int u, int parent, const vector<vector<pair<int, int>>>& weightedTree) { int max1 = 0, max2 = 0; for (auto [v, w] : weightedTree[u]) { if (v == parent) continue; int current = dfsDP(v, u, weightedTree) + w; if (current > max1) { max2 = max1; max1 = current; } else if (current > max2) { max2 = current; } } diameter = max(diameter, max1 + max2); return max1; } int main() { int n; cin >> n; vector<vector<pair<int, int>>> weightedTree(n); for (int i = 1; i < n; ++i) { int u, v, w; cin >> u >> v >> w; weightedTree[u].emplace_back(v, w); weightedTree[v].emplace_back(u, w); } dfsDP(0, -1, weightedTree); cout << "Tree diameter: " << diameter << endl; return 0; }3. 从LeetCode真题到实际应用
让我们看几个典型问题，理解如何应用这些概念。
3.1 LeetCode 1245. 树的直径
这是一道典型的求树直径的问题，可以直接应用我们前面讨论的算法。
class Solution { public: int treeDiameter(vector<vector<int>>& edges) { if (edges.empty()) return 0; vector<vector<int>> tree(edges.size() + 1); for (auto& e : edges) { tree[e[0]].push_back(e[1]); tree[e[1]].push_back(e[0]); } auto [u, _] = findFarthest(tree, 0); auto [v, diameter] = findFarthest(tree, u); return diameter; } pair<int, int> findFarthest(const vector<vector<int>>& tree, int start) { vector<int> dist(tree.size(), -1); queue<int> q; q.push(start); dist[start] = 0; int farthest = start, max_dist = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : tree[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); if (dist[v] > max_dist) { max_dist = dist[v]; farthest = v; } } } } return {farthest, max_dist}; } };3.2 医院选址问题：重心的实际应用
医院选址问题要求找到一个位置，使得所有居民到达医院的总距离最小。这正是树的重心的典型应用场景。
#include <iostream> #include <vector> using namespace std; struct Node { int population; int left, right; }; vector<Node> nodes; vector<vector<int>> tree; vector<int> subtree_pop; vector<long long> total_dist; int n; void buildTree() { tree.resize(n + 1); for (int i = 1; i <= n; ++i) { if (nodes[i].left) { tree[i].push_back(nodes[i].left); tree[nodes[i].left].push_back(i); } if (nodes[i].right) { tree[i].push_back(nodes[i].right); tree[nodes[i].right].push_back(i); } } } void dfsSize(int u, int parent) { subtree_pop[u] = nodes[u].population; for (int v : tree[u]) { if (v == parent) continue; dfsSize(v, u); subtree_pop[u] += subtree_pop[v]; } } void dfsDist(int u, int parent, int depth) { total_dist[1] += nodes[u].population * depth; for (int v : tree[u]) { if (v == parent) continue; dfsDist(v, u, depth + 1); } } void dfsDP(int u, int parent) { for (int v : tree[u]) { if (v == parent) continue; total_dist[v] = total_dist[u] + subtree_pop[1] - 2 * subtree_pop[v]; dfsDP(v, u); } } int main() { cin >> n; nodes.resize(n + 1); subtree_pop.resize(n + 1); total_dist.resize(n + 1); for (int i = 1; i <= n; ++i) { cin >> nodes[i].population >> nodes[i].left >> nodes[i].right; } buildTree(); dfsSize(1, 0); dfsDist(1, 0, 0); dfsDP(1, 0); long long min_total = total_dist[1]; for (int i = 2; i <= n; ++i) { if (total_dist[i] < min_total) { min_total = total_dist[i]; } } cout << "Minimum total distance: " << min_total << endl; return 0; }4. 高级应用与性能优化
4.1 处理大规模树的技巧
当处理节点数超过1e5的大规模树时，需要考虑以下优化：
- 使用邻接表而非邻接矩阵：节省空间，提高访问效率
- 避免递归爆栈：可以改用迭代DFS或BFS
- 并行计算：对于独立子树的计算可以考虑并行处理
// 迭代版DFS示例 void iterativeDFS(int root) { stack<pair<int, int>> st; // {node, parent} st.push({root, -1}); while (!st.empty()) { auto [u, parent] = st.top(); st.pop(); // 处理u节点 for (int v : tree[u]) { if (v != parent) { st.push({v, u}); } } } }4.2 动态树的重心与直径
如果树结构会动态变化（添加/删除边），我们需要能高效维护重心和直径的数据结构。这时可以考虑使用Link-Cut Tree或Euler Tour等高级数据结构。
// 动态维护树直径的简化示例 class DynamicTreeDiameter { set<int> leaves; vector<unordered_set<int>> tree; int endpoint1, endpoint2, diameter; public: DynamicTreeDiameter(int n) : tree(n), endpoint1(0), endpoint2(0), diameter(0) {} void addEdge(int u, int v) { tree[u].insert(v); tree[v].insert(u); updateDiameter(); } void removeEdge(int u, int v) { tree[u].erase(v); tree[v].erase(u); updateDiameter(); } private: void updateDiameter() { // 实现动态更新直径的逻辑 // 通常需要重新计算或部分更新 } };在实际项目中，我曾遇到需要实时更新树结构并查询直径的需求，最终采用了基于LCA（最低公共祖先）的优化方案，将每次查询的时间复杂度降到了O(1)，虽然预处理需要O(n log n)的时间，但对于频繁查询的场景非常有效。
