ZOJ 3820 消防站建設：樹直徑分治與雙源 BFS

問題描述

給定 n 個節點的樹（邊長為 1），需在兩個節點建立消防站，使得所有節點到最近消防站的最大距離最小。輸出最小最大距離及兩個消防站節點編號。

核心洞察

最優解必定與樹的直徑相關。樹的直徑是樹上最長路徑，其端點通過兩次 BFS/DFS 可求得。直徑中點（或中間邊）是關鍵分割點。

算法流程

1. 任意節點 BFS 找到直徑一端 st
2. 從 st BFS 找到直徑另一端 ed，記錄路徑父節點，重構直徑路徑數組 s[]
3. 直徑長度 L = depth[ed] + 1
   • 若 L 為奇數：中間是一條邊 (l, r)，刪除該邊分成兩棵子樹
   • 若 L 為偶數：中間是一個節點 mid，將 mid 分配給兩側子樹（複製節點或標記）
4. 對兩棵子樹分別求直徑中點，即為最優消防站位置
5. 答案為 max(子樹1半徑, 子樹2半徑)

關鍵代碼片段（C++）

int bfs(int st) {
    queue q; q.push(st);
    vis[st] = 1; d[st] = 0; fa[st] = -1;
    int ans = st;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].v;
            if (vis[v]) continue;
            vis[v] = 1; d[v] = d[u] + 1; fa[v] = u;
            if (d[v] > d[ans]) ans = v;
            q.push(v);
        }
    }
    // 重構路徑
    top = 0; int u = ans;
    while (u != -1) { s[top++] = u; u = fa[u]; }
    return ans;
}

// 主邏輯
int st = bfs(1), ed = bfs(st);
int depth = d[ed] + 1;
int l = s[depth/2 - 1], r = s[depth/2]; // 中間邊/節點
// 刪除中間邊，重建圖，對兩側分別 BFS 求直徑中點...

關鍵細節處理

• 奇數直徑：直接刪除中間邊，兩側獨立求解
• 偶數直徑：中間節點需「分身」，一側包含該節點，另一側也包含（通過訪問標記控制）
• 最終答案可能兩個消防站位於同一節點（退化情況）
• 輸出格式：距離、站點1、站點2（若相同則輸出相鄰節點）

複雜度分析

• 多次 BFS：O(n)
• 總體：O(n)，完美解決 n ≤ 200,000 規模

此題是樹分治與直徑性質的經典應用，將雙源覆蓋問題轉化為直徑分割子問題，體現了樹算法的優雅性。