基本思想是先用dfs求出整棵树的直径以及直径上的每个点
然后划分应该断开直径中的边，以保证剩下子树的直径都变小
接着使用树形dp预处理出断开直径上的每条边后，剩下子树的直径
最后遍历直径上的边，计算断开后两子树直径差的绝对值最小值即可
C++代码如下：
#include <bits/stdc++.h> // C++万能头文件
using namespace std;
using pii = pair<int, int>; // 每条边的右端点v和权重
const int N = 1e6 + 1; // 点数最大值
vector<pii> 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]; // 断开边<v,u>，u指向e，v指向s
ans = min(ans, abs(res[u][0] - res[v][1]));
u = v;
}
cout << ans << "\n";
return 0;
}
g++编译通过，且通过测试用例，望采纳~
