ZOJ 3820 Building Fire Stations：樹上雙消防站選址 (二分答案 + BFS 直徑)

問題重述

給定一棵 N 節點樹 (N ≤ 200,000)，邊長均為 1。需在兩個不同節點建消防站，使任意節點到最近消防站的距離的 最大值 最小。輸出該最小最大距離及任意一組最優建站節點。

關鍵結論：最優消防站必在樹的直徑上

證明略，結論為：最優解的兩個站點必位於樹直徑的兩端附近。因此可對答案 (最大距離 L) 二分，檢查是否可行。

檢查函數 check(L)

1. 任意節點 (如 1) BFS 找最遠點 u (直徑一端)。
2. 從 u BFS 找最遠點 v (直徑另一端)，記錄父節點 pre[]。
3. 從 u 沿父節點向 v 走 L 步 → 站點 s；從 v 向 u 走 L 步 → 站點 t。若走到根仍不足 L 步，說明 L 過大，直接可行。
4. 以 s 和 t 為源頭多源 BFS，計算所有節點到最近站點距離。若最大距離 ≤ L，返回 true。

核心代碼片段

bool check(int L, int& s, int& t) {
    // 1. 找直徑端點 u, v
    int u = bfs(1);
    int v = bfs(u); // bfs 返回最遠點，並填充 pre[]
    // 2. 確定站點
    s = u; for (int i=0;i L) return false;
    return true;
}

完整流程

int low=0, high=n, ans=n, fs, ft;
while (low <= high) {
    int mid = (low+high)/2;
    int s, t;
    if (check(mid, s, t)) { ans=mid; fs=s; ft=t; high=mid-1; }
    else low=mid+1;
}
cout << ans << ' ' << fs << ' ' << ft << '\n';

複雜度與優化

• 單次 check: 3 次 BFS → O(N)。
• 二分 log N 次 → 總 O(N log N)，N=2e5 時約 3e6 操作，2 秒內輕鬆通過。
• 輸入量大，建議用快速讀入 (自定義 nextInt() 或 fread)。

樣例解析

輸入：
2
4
1 2
1 3
1 4
5
1 2
2 3
3 4
4 5
輸出：
1 1 2
1 2 4
解釋：星形樹半徑 1，建在中心 1 和任意葉子；鏈長 5，建在 2、4 使最大距離為 1。