P1099 [NOIP 2007 提高组] 树网的核

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int n, s;
vector<pair<int, int>> adj[MAXN];
int D[MAXN][MAXN];        // 任意两点间的距离
int pre[MAXN], dd[MAXN];  // dfsFar 记录的父亲与距离

// 从 x 出发遍历整棵树，记录到每个结点的距离 dd[] 与父亲 pre[]
void dfsFar(int x, int fa, int d) {
    pre[x] = fa;
    dd[x] = d;
    for (auto [y, w] : adj[x]) {
        if (y == fa) continue;
        dfsFar(y, x, d + w);
    }
}

// 从 src 出发求到所有结点的距离，填进 D
void dfsDist(int x, int fa, int d, int src) {
    D[src][x] = d;
    for (auto [y, w] : adj[x]) {
        if (y == fa) continue;
        dfsDist(y, x, d + w, src);
    }
}

int main() {
    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++) dfsDist(i, 0, 0, i);

    // 两次遍历找直径的两端
    dfsFar(1, 0, 0);
    int u = 1;
    for (int i = 2; i <= n; i++) if (dd[i] > dd[u]) u = i;
    dfsFar(u, 0, 0);
    int v = u;
    for (int i = 1; i <= n; i++) if (dd[i] > dd[v]) v = i;

    // 回溯出直径上的结点序列（依次是 v, ..., u）
    vector<int> path;
    for (int x = v; x != 0; x = pre[x]) path.push_back(x);
    int k = (int)path.size();

    // 每个结点在直径上的挂点位置与高度
    vector<int> pos(n + 1, 0), h(n + 1, INF);
    for (int x = 1; x <= n; x++) {
        for (int i = 0; i < k; i++) {
            if (D[path[i]][x] < h[x]) { h[x] = D[path[i]][x]; pos[x] = i; }
        }
    }

    // 沿直径的前缀距离（从 v 算起）
    vector<int> dis(k, 0);
    for (int i = 1; i < k; i++) dis[i] = D[path[0]][path[i]];

    int ans = INF;
    for (int l = 0; l < k; l++) {
        int r = l;
        while (r + 1 < k && dis[r + 1] - dis[l] <= s) r++;
        int ecc = 0;
        for (int x = 1; x <= n; x++) {
            int p = pos[x], d;
            if (p < l) d = h[x] + dis[l] - dis[p];
            else if (p > r) d = h[x] + dis[p] - dis[r];
            else d = h[x];
            ecc = max(ecc, d);
        }
        ans = min(ans, ecc);
    }
    cout << ans << '\n';
    return 0;
}