https://www.acwing.com/problem/content/1075/
输出树的中心(该点到树中其他结点的最远距离最近)。
时间复杂度 \(O(n)\)。
#include <bits/stdc++.h> using namespace std; #define LL long long int main(){ ios::sync_with_stdio(false);cin.tie(0); int n; cin >> n; vector < vector < array<LL, 2> > > e(n + 1); for (int i = 1; i < n; i ++ ){ int u, v, w; cin >> u >> v >> w; e[u].push_back({w, v}); e[v].push_back({w, u}); } vector <LL> d1(n + 1), d2(n + 1), s1(n + 1), s2(n + 1); function<void(int, int)> dfs1 = [&](int u, int fa){ for (auto [w, v] : e[u]){ if (v == fa) continue; dfs1(v, u); LL x = d1[v] + w; if (x > d1[u]){ d2[u] = d1[u], s2[u] = s1[u]; d1[u] = x, s1[u] = v; } else if (x > d2[u]){ d2[u] = x, s2[u] = v; } } }; dfs1(1, 0); vector <LL> up(n + 1); function<void(int, int)> dfs2 = [&](int u, int fa){ for (auto [w, v] : e[u]){ if (v == fa) continue; if (s1[u] == v) up[v] = max(up[u], d2[u]) + w; else up[v] = max(up[u], d1[u]) + w; dfs2(v, u); } }; dfs2(1, 0); LL ans = 1e18; for (int i = 1; i <= n; i ++ ) ans = min(ans, max(d1[i], up[i])); cout << ans << "\n"; return 0; }