BZOJ 2599 IOI2011 Race 樹分治求指定長度路徑最小邊數

BZOJ 2599 IOI2011 Race 樹分治算法詳解

給定 N (≤200,000) 節點樹，邊有長度，求長度恰好等於 K (≤1,000,000) 的路徑中邊數最小值。樹分治核心：選重心分解，統計過重心路徑，遞歸處理子樹。

核心算法流程

1. 尋找重心：遞歸計算子樹大小，找到移除後最大連通塊最小的節點
2. 收集路徑信息：DFS 記錄從重心到各節點的距離和深度(邊數)
3. 統計配對：對每個子樹，先查詢當前全局數組中是否存在互補距離，更新答案；再將子樹路徑加入全局數組
4. 遞歸分治：標記重心為禁用，遞歸處理各子樹

關鍵優化：最小值不支持區間減法

統計所有距離和為 K 的路徑對，記錄各深度出現次數。最後掃描深度數組找最小有效深度。避免了難以處理的"最小值減法"問題。

C++ 代碼實現 (關鍵片段)

void Find_Centre_Of_Gravity(int x, int size, int &cg) {
    // 計算子樹大小，判斷是否為重心
}

void DFS1(int x, int d, int deep, int from) {
    // 記錄距離 dis[x] 和深度 dpt[x]
}

void Calculate(int x, int flag) {
    // 收集當前子樹所有節點 (距離, 深度)
    // 排序後雙指針查找距離和為 K 的配對
    // ans[深度和] += flag (1: 加入, -1: 排除當前子樹內部配對)
}

void Tree_Divide_And_Conquer(int root, int size) {
    int cg; Find_Centre_Of_Gravity(root, size, cg);
    DFS1(cg, 0, 0, 0);
    Calculate(cg, 1);
    for (子樹) {
        標記邊禁用;
        Calculate(子樹根, -1);  // 排除子樹內部配對
        Tree_Divide_And_Conquer(子樹根, 子樹大小);
    }
}

複雜度分析

• 時間：O(N log² N) - 分治層數 log N，每層排序 O(N log N)
• 空間：O(N) - 存圖、距離、深度、臨時棧數組

工程踩坑記錄

• 數組大小需開 200200 × 2 (雙向邊)
• 遞歸深度可能達 N，需增棧或改迭代
• 長度和為 K 的配對統計需仔細處理 flag 正負抵消
• 最終答案從 1 到 N-1 掃描 ans 數組找第一個非零值