UVA 11695：Flight Planning - 修改一條邊使樹直徑最小

問題描述

給定一棵 n ≤ 2500 節點的樹。允許刪除一條邊並添加一條新邊（保持為樹），使新樹的直徑最小。輸出最小直徑、被刪除的邊、新增的邊。

核心觀察

1. 刪除邊 (u, v) 將樹分為兩棵子樹 T1, T2。
2. 新增邊必須連接 T1 和 T2 的某兩個節點。為使直徑最小，新邊應連接兩棵子樹的 重心（或直徑中點）。
3. 新樹直徑 = max( diam(T1), diam(T2), ceil(diam(T1)/2) + 1 + ceil(diam(T2)/2) )。

算法流程

1. 枚舉每條邊作為被刪除邊。
2. 對兩棵子樹分別用兩次 BFS 求直徑及其中點（重心）。
3. 計算新直徑，維護全局最優解。

代碼實現 (關鍵邏輯)

int bfs_farthest(int start, int ban_u, int ban_v, int &far) {
    // BFS 找最遠點 far，返回距離，忽略禁用邊 (ban_u, ban_v)
}

pair<int,int> get_center(int u, int ban_u, int ban_v) {
    int far1 = bfs_farthest(u, ban_u, ban_v, far1);
    int far2 = bfs_farthest(far1, ban_u, ban_v, far2);
    // 回溯路徑找中點
    vector<int> path;
    while (far2 != -1) { path.push_back(far2); far2 = pre[far2]; }
    return {path[path.size()/2], (int)path.size() - 1}; // 中點、直徑長度
}

void solve() {
    for (each edge (u,v)) {
        auto [c1, d1] = get_center(u, u, v);
        auto [c2, d2] = get_center(v, u, v);
        int newDiam = max({d1, d2, (d1+1)/2 + 1 + (d2+1)/2});
        if (newDiam < best) update answer;
    }
}

複雜度

• 枚舉 n-1 條邊，每次 4 次 BFS：O(n^2)，n=2500 時約 2.5e7 操作，可接受。

總結

本題關鍵在於識別「連接兩子樹重心」能使新直徑最小，並利用 BFS 求樹直徑與中點。屬於樹上經典問題變體。