ZOJ 3820 Building Fire Stations：樹的直徑與二分查找解法詳解

問題背景

在 Marjar 大學的校園裡，有 N 棟建築，由 N-1 條長度為 1 的雙向道路連接，構成一棵樹。校長 Edward 想在兩棟不同的建築設立消防站，使得任意建築到最近消防站的最長距離最小化。這是一個經典的樹上雙中心問題。

核心觀察：最優解一定在直徑上

若只設一個消防站，最優位置是樹的直徑中點（或重心）。對於兩個消防站，經過反證法可以證明：兩個最優消防站必定位於樹的直徑上。這大大縮小了搜索空間。

解題思路

1. 找出樹的直徑：兩次 BFS/DFS。先從任意節點找到最遠端點 u，再從 u 找到最遠端點 v，路徑 u→v 即為直徑。
2. 將直徑上的節點存入數組ans[]，長度為 sz。
3. 二分答案：檢查某個最大距離 mid 是否可行。可行條件：在直徑上選兩點 ans[mid] 和 ans[sz-mid-1] 作為消防站，對全樹 BFS，若所有節點到最近消防站距離 ≤ mid，則可行。
4. 輸出最小可行 mid 及對應的兩個節點。

關鍵代碼片段

// 兩次 BFS 找直徑端點與長度
void bfs(int s, int &x, int &l) {
    memset(dist, -1, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    dist[s] = 0; x = s; l = 0;
    queue<int> q; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            pre[v] = u;
            q.push(v);
            if (dist[v] > l) { l = dist[v]; x = v; }
        }
    }
}

// 檢查 mid 是否可行
bool check(int mid, int &ans1, int &ans2) {
    ans1 = ans[mid];
    ans2 = ans[sz - mid - 1];
    bfs1(ans1, dist);
    bfs1(ans2, dist1);
    for (int i = 1; i <= n; i++)
        if (min(dist[i], dist1[i]) > mid) return false;
    return true;
}

// 主程序二分
int l = 0, r = ll/2 + 1, res, ans1, ans2;
while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid, ans1, ans2)) { res = mid; r = mid - 1; }
    else l = mid + 1;
}
check(res, ans1, ans2);
printf("%d %d %d\n", res, ans1, ans2);

複雜度分析

• 找直徑：O(N)
• 每次 check 兩次 BFS：O(N)
• 二分次數：O(log N)
• 總複雜度：O(N log N)，滿足 N ≤ 200,000。

常見誤區

嘗試「找直徑中點分成兩棵子樹，再分別找子樹直徑中心」的貪心策略，雖然直觀，但並不總能得到最優解，實測會 WA。二分法雖然代碼稍長，但邏輯嚴密、通用性強。