用C搞定树的重心与直径从LeetCode刷题到解决「医院选址」实际问题树结构在算法竞赛和实际应用中无处不在从社交网络的关系图谱到城市交通的路网规划理解树的特性往往能帮助我们高效解决问题。本文将深入探讨树的两个核心概念——重心与直径并展示如何用C实现相关算法最终解决类似「医院选址」的实际问题。1. 树的重心概念与算法实现树的重心是树中一个特殊的节点删除该节点后剩余子树的最大节点数最小。这个概念在优化问题中非常有用比如在网络布局中寻找关键节点。1.1 重心的数学定义与性质树的重心有以下重要性质一棵树最多有两个重心且它们相邻以重心为根时所有子树的大小不超过整棵树的一半树中所有点到重心的距离和最小这些性质使得重心成为许多优化问题的理想选择点比如我们后面会讨论的医院选址问题。1.2 寻找重心的DFS算法我们可以通过一次DFS遍历找到树的重心。关键思路是对于每个节点计算删除它后最大子树的节点数然后选择使这个值最小的节点。#include iostream #include vector using namespace std; const int N 1e5 10; vectorint 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; pairint, int findFarthest(const vectorvectorint tree, int start) { vectorint dist(tree.size(), -1); queueint 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 vectorvectorint 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 vectorvectorpairint, 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; vectorvectorpairint, 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(vectorvectorint edges) { if (edges.empty()) return 0; vectorvectorint 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; } pairint, int findFarthest(const vectorvectorint tree, int start) { vectorint dist(tree.size(), -1); queueint 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; }; vectorNode nodes; vectorvectorint tree; vectorint subtree_pop; vectorlong 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) { stackpairint, 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 { setint leaves; vectorunordered_setint 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)的时间但对于频繁查询的场景非常有效。