求大神解答c++题目

基本思想是先用dfs求出整棵树的直径以及直径上的每个点

然后划分应该断开直径中的边，以保证剩下子树的直径都变小

接着使用树形dp预处理出断开直径上的每条边后，剩下子树的直径

最后遍历直径上的边，计算断开后两子树直径差的绝对值最小值即可

C++代码如下：

#include // C++万能头文件

using namespace std;

using pii = pair; // 每条边的右端点v和权重

const int N = 1e6 + 1; // 点数最大值

vector edges[N]; // 每个左端点u连接的边

long d[N]; // 以u为端点的最远距离

int pre[N]; // 最远路径上u的前驱节点

int e = 0; // e为dfs中起点出发可达的最远节点

long res[N][2]; // 统计删边后各子树中的直径

// dfs中d[u]表示到达u的最长距离

void dfs(int u, int father) {

    if (d[u] > d[e]) // 到达u的距离更长

        e = u; // 更新最远节点

    for (auto [v, w] : edges[u]) { // 遍历连接u的所有边

        if (v == father) continue; // 防止重复遍历

        pre[v] = u; // u-->v，v的前驱为u

        d[v] = d[u] + w;

        dfs(v, u);

    }

}

// 树形dp中d[u]表示u出发的最长距离

void dp(int u, int father, int flag) { // flag为0表示指向e，为1表示指向s

    for (auto [v, w] : edges[u]) { // 遍历连接u的所有边

        if (v == father) continue; // 防止重复遍历

        dp(v, u, flag); // 计算子树d[v]

        res[u][flag] = max(res[u][flag], res[v][flag]); // 先继承子树中的直径

        res[u][flag] = max(res[u][flag], d[u] + d[v] + w);

        d[u] = max(d[u], d[v] + w); // 再统计u出发的子树中通过u的最长距离

    }

}

int main() {

    int n;

    cin >> n;

    for (int i = 1; i < n; ++i) {

        int v = i + 1, u, w;

        cin >> u >> w;

        edges[u].emplace_back(v, w);

        edges[v].emplace_back(u, w);

    }

    if (n <= 2) {

        cout << "0\n";

        return 0;

    }

    dfs(1, -1); // 先计算从1出发的最远节点

    int s = e; // s为直径的一个端点

    memset(d, 0, sizeof(d));

    memset(pre, -1, sizeof(pre));

    dfs(s, -1); // 再计算从s出发的最远节点

    memset(d, 0, sizeof(d));

    dp(s, -1, 0); // 初始为s，统计指向e的各子树的直径

    memset(d, 0, sizeof(d));

    dp(e, -1, 1); // 初始为s，统计指向s的各子树的直径

    long ans = LONG_MAX;

    int u = e; // 遍历直径上每个节点

    while (u != s) {

        int v = pre[u]; // 断开边，u指向e，v指向s

        ans = min(ans, abs(res[u][0] - res[v][1]));

        u = v;

    }

    cout << ans << "\n";

    return 0;

}

g++编译通过，且通过测试用例，望采纳~