P1099 [NOIP 2007 提高组] 树网的核 - 洛谷
题目大意
给你一个无根树的树网，在直径上求一段路径其长度都不超过s使得这段路径的偏心距最小，偏心距是指所有点到该路径的最长距离
题目主要实现思路
首先dfs两次求出树的直径，并且记录直径的路径，遍历直径上的每一个点，因为要求长度不超过s，所以可以固定一端，另一端找到最大的位置（可以证明其他路径的偏心距一定大于这种情况，可以忽略，答案一定是最大的满足位置），因此可以用双指针，然后将该路径的点都设为一访问，然后遍历一遍，求出该段路径的偏心距，然后取最小即可
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e6 + 10;const int mod = 998244353;void solve(){ int n, s; cin >> n >> s; vector<vector<pair<int, int>>> adj(n + 1); for (int i = 0; i < n - 1; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } vector<int> dis(n + 1, 0); vector<int> ida(n + 1); vector<int> vit(n + 1); int mx = 0, mxd = 0; auto dfs = [&](auto &&dfs, int u, int fa, int dep) -> void { ida[u] = fa; for (auto &[nu, val] : adj[u]) { if (fa != nu && !vit[nu]) { dis[nu] = dis[u] + val; if (dis[mx] < dis[nu]) { mx = nu; } dfs(dfs, nu, u, dep + val); } } }; dfs(dfs, 1, 0, 0); int st = mx; mxd = 0; mx = 0; dis[st] = 0; dfs(dfs, st, 0, 0); auto p = ida;//子节点也会变化 int ed = mx; int x = 0, ans = INT_MAX; auto nwdis=dis;//后面进行dfs算偏心距的时候dis数组会变化，所以提前存下来更好 for (int i = ed, j = ed; i; i = p[i])//遍历这段路径 { while (p[j] && nwdis[i] - nwdis[p[j]] <= s)//找到固定左节点最长的路径 { j = p[j]; } fill(vit.begin(), vit.end(), 0); for (int k = i; k != p[j]; k = p[k])//将该路径上所有的点都标记 { vit[k] = 1; } int res = 0; for (int k = i; k != p[j]; k = p[k]) { dis[k] = 0; mx = 0; dfs(dfs, k, 0, 0); res = max(res, dis[mx]);//找到该段路径的偏心距 } ans = min(ans, res); } cout << ans << '\n';}signed main(){ ios::sync_with_stdio(0), cin.tie(0); cout.tie(0); int T; T = 1; // cin >> T; while (T--) solve(); return 0;}