题解 | 树网的核

alt

题干解析

题设定义：针对一个无根无向有权树：

树中两点的距离为两点间路径的权值之和。
树的直径即为树中两点间最大的距离。
树中节点到路径的距离定义为点到路径上任意一点距离的最小值。
确定直径上一条长不超过s的核后偏心距（EEC）定义为图中任意节点到该路径（核）的距离的最大值。题设给我们树的邻接数据以及s的大小，要求我们计算符合要求的核对应的EEC的最小值。

算法思路

寻找直径

首先我们需要找到树的直径，由于树中任意两节点有且仅有一条路径，使用弗洛伊德算法能够求出所有树中任意两点间的路径距离。
基于此我们找到最大的路径长度然后找出所有符合条件的路径节点便可以得到树的直径。

对直径路径进行枚举

在枚举前我们先构造路径权值前缀（pre）与后缀（post）和，中间路径长度便为D - pre[left] - post[right]。同时我们需要注意到树的枝杈也会一定程度上影响偏心距的大小，因此还需要记录各路径节点上枝杈的最大长度（branch），由于弗洛伊德路径矩阵存放的是一条路径的下一跳，只要下一跳不在直径上便是枝杈，记录最大值即可。
以上准备工作做好后直接枚举left和right，选取符合要求的路径左右端点，ECC就在pre[left]，post[right]，以及所选路径上长度最大的枝杈的值中选最大的，题设要求的结果就在所有可能的ECC中找最小的即可。

实现代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, s;
    cin >> n >> s;
    vector adj(n, vector(n, 1000000));
    vector next(n, vector(n, -1)); // 路径下一跳
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        adj[u][v] = w;
        adj[v][u] = w;
        next[u][v] = v;
        next[v][u] = u;
    }
    for (int i = 0; i < n; ++i) {
        adj[i][i] = 0;
        next[i][i] = -1;
    }

    // 弗洛伊德
    auto dis = adj; // 距离矩阵

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            if (dis[i][k] == 1000000) continue;
            for (int j = 0; j < n; ++j) {
                if (dis[k][j] == 1000000) continue;
                if (const int d = dis[i][k] + dis[k][j]; d < dis[i][j]) {
                    dis[i][j] = d;
                    next[i][j] = next[i][k];
                }
            }
        }
    }
    // 寻找直径
    vector<vector<int>> DPath;
    int D = 0;
    for (int i = 0; i < n; ++i) {
        D = max(D, *ranges::max_element(dis[i]));
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dis[i][j] == D) {
                int from = i, to = j;
                dis[j][i] = 0; // 防重复
                vector<int> path; path.push_back(from);
                while (from != to) {
                    from = next[from][to];
                    path.push_back(from);
                }
                DPath.push_back(path);
            }
        }
    }
    // 处理核
    int ans = 1000000;
    for (auto path : DPath) {
        vector<int> E;
        const int n_ = path.size();
        for (int i = 0; i < n_ - 1; ++i) E.push_back(adj[path[i]][path[i + 1]]);
        vector<int> pre(n_, 0), post(n_, 0);
        for (int i = 0; i < n_ - 1; ++i) {
            pre[i + 1] = pre[i] + E[i]; // 前缀和
            post[n_ - 2 - i] = post[n_ - 1 - i] + E[n_ - 2 - i]; // 后缀和
        }
        
        // 分支情况
        vector onPath(n, false);
        for (auto v : path) onPath[v] = true;
        vector branch(n_, 0);
        for (int i = 0; i < n_; ++i) {
            int from = path[i];
            for (int to = 0; to < n; ++to) {
                if (next[from][to] == -1 || onPath[next[from][to]]) continue;
                branch[i] = max(branch[i], dis[from][to]);
            }
        }

        // 枚举
        for (int left = 0; left < n_; ++left) {
            for (int right = n_ - 1; right >= left; --right) {
                if (D - pre[left] - post[right] > s) continue;
                int branchMax = -1;
                for (int i = left + 1; i <= right - 1; ++i) branchMax = max(branchMax, branch[i]);
                int ECC = max(branchMax, max(pre[left], post[right]));
                ans = min(ans, ECC);
            }
        }
    }
    cout << ans;
    return 0;
}//*/