题目理解

我们有一棵 $n$ 个节点的树，边带权（交通费用）。
我们可以删除一条边，并在相同位置重建一条相同权值的边（实际上相当于可以改变树的形态，但保持边集不变）。

目标是：最小化改造后树的直径（即两城市之间的最大交通费用）。

核心思路

1. 问题转化

原问题等价于：
在树中删除一条边 $(u,v)$，得到两棵子树 $T_1$ 和 $T_2$，然后用一条权值相同的边连接这两棵树，使得新树的直径最小。

新树的直径可能出现在三种情况中：

1. 完全在 $T_1$ 中
2. 完全在 $T_2$ 中
3. 跨越新边，由 $T_1$ 中某点到 $T_2$ 中某点

2. 关键观察

设删除边 $(u,v)$ 权值为 $w$，$T_1$ 的直径为 $d_1$，$T_2$ 的直径为 $d_2$，
$T_1$ 中距离 $u$ 最远的点距离为 $r_1$，$T_2$ 中距离 $v$ 最远的点距离为 $r_2$。

则新树直径为：

我们要最小化这个值。

3. 算法步骤

1. 求原树直径：两次 DFS 找到直径路径
2. 预处理直径路径信息：
   • 对于直径上的每个点，求它到非直径节点的最远距离
   • 预处理直径路径上的前缀和后缀信息
3. 枚举删除的边（在直径上枚举即可）：
   • 计算断开后两部分的直径
   • 计算连接后的新直径
   • 更新答案

代码解析

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 4;
int n, dist[N], sum[N], p;
int vis[N], sum2[N], ans = 2e9;
int pre[N][2], nxt[N][2];      // pre[i][0]:父节点, pre[i][1]:边权
int st[N][2], st2[N][2];       // 存储直径路径上的关键信息

struct edge {
    int v, w;
};
vector<edge> e[N];
vector<int> rec;

// 第一次DFS：计算距离并记录父节点
void dfs(int x, int fa) {
    for (edge i : e[x]) {
        if (i.v == fa) continue;
        dist[i.v] = dist[x] + i.w;
        pre[i.v][0] = x, pre[i.v][1] = i.w;
        dfs(i.v, x);
    }
}

// 第二次DFS：标记连通块并计算距离
void dfs2(int x, int fa) {
    rec.emplace_back(x);
    vis[x] = 1;
    for (edge i : e[x]) {
        if (vis[i.v]) continue;
        dist[i.v] = dist[x] + i.w;
        if (i.v == fa) continue;
        dfs2(i.v, x);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    
    // 建图
    for (int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    
    // 第一次DFS：从节点1开始找最远点
    dfs(1, 0);
    int mx = 0, id = 0, ed = 0;
    for (int i = 1; i <= n; ++i)
        if (mx < dist[i]) mx = dist[i], id = i;
    
    // 第二次DFS：从id开始找直径的另一端点
    memset(dist, 0, sizeof dist);
    dfs(id, 0);
    mx = 0;
    for (int i = 1; i <= n; ++i)
        if (mx < dist[i]) mx = dist[i], ed = i;
    
    // 标记直径路径并计算前缀和
    for (int i = ed; i != id; i = pre[i][0]) {
        vis[i] = 1, vis[pre[i][0]] = 1;
        sum[pre[i][0]] += sum[i] + pre[i][1];
    }
    
    // 处理直径路径上每个点对应的分支信息
    for (int i = 1; i <= n; ++i) dist[i] = sum[i];
    p = ed;
    int dis = 0;
    
    // 正向处理：从ed到id
    for (int i = ed;; i = pre[i][0]) {
        rec.clear();
        dfs2(i, 0);  // 标记当前连通块
        
        for (int j : rec) dis = max(dis, dist[j]);
        
        // 寻找重心（使最大距离最小化的连接点）
        while (abs(dis - sum[p] - sum[p]) > abs(dis - sum[pre[p][0]] - sum[pre[p][0]]))
            p = pre[p][0];
            
        st[i][0] = p, st[i][1] = dis;  // 存储最优连接点和对应直径
        
        if (i == id) break;
    }
    
    // 反向处理：从id到ed
    memset(vis, 0, sizeof vis);
    for (int i = ed; i != id; i = pre[i][0]) {
        vis[i] = 1, vis[pre[i][0]] = 1;
        nxt[pre[i][0]][0] = i, nxt[pre[i][0]][1] = pre[i][1];
    }
    
    for (int i = id; i != ed; i = nxt[i][0])
        sum2[nxt[i][0]] += sum2[i] + nxt[i][1];
    
    for (int i = 1; i <= n; ++i) dist[i] = sum2[i];
    p = id;
    dis = 0;
    
    for (int i = id;; i = nxt[i][0]) {
        rec.clear();
        dfs2(i, 0);
        
        for (int j : rec) dis = max(dis, dist[j]);
        
        while (abs(dis - sum2[p] - sum2[p]) > abs(dis - sum2[nxt[p][0]] - sum2[nxt[p][0]]))
            p = nxt[p][0];
            
        st2[i][0] = p, st2[i][1] = dis;
        
        if (i == ed) break;
    }
    
    // 枚举删除的边，计算新直径
    for (int i = id;; i = nxt[i][0]) {
        int v = nxt[i][0];
        int w = nxt[i][1];
        
        // 计算三种情况的直径取最大值
        int case1 = st2[i][1];                          // T1的直径
        int case2 = st[v][1];                           // T2的直径  
        int case3 = max(st2[i][1] - sum2[st2[i][0]], sum2[st2[i][0]]) 
                   + w 
                   + max(st[v][1] - sum[st[v][0]], sum[st[v][0]]);  // 跨越新边的路径
        
        ans = min(ans, max({case1, case2, case3}));
        
        if (i == ed) break;
    }
    
    cout << ans;
    return 0;
}

关键算法说明

1. 树的直径求解

• 两次DFS：$O(n)$ 时间找到直径端点
• 第一次从任意点找到最远点
• 第二次从该点找到真正的直径另一端

2. 分支最远距离计算

对于直径上的每个点，计算它到非直径节点的最远距离，用于后续连接时的半径计算。

3. 最优连接点选择

通过预处理找到每棵子树的"重心"，使得连接后的跨越路径长度最小。

复杂度分析

• 两次DFS求直径：$O(n)$
• 预处理分支信息：$O(n)$
• 枚举删除边：$O(n)$
• 总复杂度：$O(n)$

这种方法充分利用了树的直径性质，通过预处理和精细分类讨论，高效解决了这个看似复杂的问题。