HDU 5052 LCT：Link-Cut Tree 維護路徑最大收益

題目背景

給定一棵 N 個節點的樹（N ≤ 50000），每個節點有初始權值 W_i。需支援 Q ≤ 50000 次操作：

1. 查詢路徑 u → v 上的「最大收益」：選擇路徑上兩個節點 i, j（i 在 j 之前），使 W_j - W_i 最大；若無正收益輸出 0。
2. 查詢完成後，路徑上所有節點權值 +V。

核心數據結構：Link-Cut Tree (LCT)

LCT 能以 O(log N) 均攤時間維護動態樹上的路徑資訊。本題利用 LCT 的 make_root + access 將任意路徑 u→v 暴露為一條 Splay 树的右鏈，從而對整條路徑進行區間查詢與修改。

節點維護的關鍵信息

每個 Splay 節點維護：

• Max、Min：子樹最大/最小權值
• mm：正向最大收益（max(val, right.Max) - left.Min 等四種組合）
• rmm：反向最大收益（用於 flip 翻轉）
• add：區間加法懶標記
• rev：翻轉懶標記

PushUp 邏輯精華

void push_up(){
    if(this==null) return;
    mm = max({ch[0]->mm, ch[1]->mm,
              max(val, ch[1]->Max) - ch[0]->Min,
              ch[1]->Max - min(val, ch[0]->Min)});
    rmm = max({ch[0]->rmm, ch[1]->rmm,
               max(val, ch[0]->Max) - ch[1]->Min,
               ch[0]->Max - min(val, ch[1]->Min)});
    Max = max(val, max(ch[0]->Max, ch[1]->Max));
    Min = min(val, min(ch[0]->Min, ch[1]->Min));
}

操作流程

// 查詢路徑 u->v 的最大收益
node[u]->make_root();        // u 變為根
node[v]->access();           // v 訪問，路徑暴露在 v 的 splay 中
printf("%d\n", node[v]->mm); // v 的 mm 即為答案

// 路徑加 V
node[v]->update_add(V);      // 對暴露的路徑整體 +V

複雜度與優化

• 單次操作 O(log N) 均攤，總複雜度 O((N+Q) log N)
• 內存池分配節點（pool[maxn]）避免頻繁 new/delete
• #pragma comment(linker, "/STACK:...") 擴大棧空間防遞歸爆棧

常見錯誤

• push_down 順序錯誤：必須先 add 再 rev
• flip 時忘記 swap(mm, rmm)
• access 結束後未 splay 導致根節點信息未更新
• 初始化 null 節點 Max=-INF, Min=INF 避免空節點干擾

總結

本題是 LCT 維護「路徑最大子段和」變體的經典應用。關鍵在於將「買入賣出」轉化為「最大值減最小值且順序固定」，並通過 mm/rmm 區分正反方向。LCT 的強大在於能將任意路徑問題轉化為 Splay 树的區間問題，配合懶標記實現高效動態維護。