HDU 4010 Query on The Trees - Link-Cut Tree (LCT) 動態樹維護路徑加權/查詢

題目大意

動態森林，支援操作：

1. Link：連接兩樹 (合併)。
2. Cut：斷開邊 (分離)。
3. Add：路徑 u-v 所有節點權值 +w。
4. Query：路徑 u-v 最大權值。

節點數 N ≤ 300000，操作數 Q 大。需 O(log N) 單次操作。

LCT 核心結構

• Splay 節點：ch[2], fa, rev, add, val, max。
• 虛擬樹 / 實邊：Access 將根到節點路徑變為實邊 (右子樹為虛邊)。
• 關鍵操作：Rotate, Splay, Access, MakeRoot, FindRoot, Link, Cut, Split (LCA)。

關鍵函數邏輯

// 推標記
void pushdown(int x) {
    if (add[x]) { add[ch[x][0]]+=add[x]; add[ch[x][1]]+=add[x]; val[ch[x][0]]+=add[x]; val[ch[x][1]]+=add[x]; max[ch[x][0]]+=add[x]; max[ch[x][1]]+=add[x]; add[x]=0; }
    if (rev[x]) { swap(ch[x][0], ch[x][1]); rev[ch[x][0]]^=1; rev[ch[x][1]]^=1; rev[x]=0; }
}

// Access：將 x 到根路徑變實邊，返回原根
int Access(int x) {
    int y = 0;
    for (; x; x = fa[y = x]) {
        Splay(x);
        // 斷開原右子樹 (虛邊)，連接 y (已處理的路徑)
        rt[ch[x][1]] = true; rt[ch[x][1] = y] = false;
        pushup(x);
    }
    return y;
}

// MakeRoot：Access 後 Splay 翻轉
void MakeRoot(int x) { Access(x); Splay(x); pushrev(x); }

// Split：提取 u-v 路徑到 u 的 Splay 中 (u 為根，v 在右子樹)
void Split(int &u, int &v) { // 返回後 u 為 LCA
    Access(v); v = 0;
    while (u) {
        Splay(u);
        if (!fa[u]) return; // u 是 LCA
        rt[ch[u][1]] = true; rt[ch[u][1] = v] = false; pushup(u);
        u = fa[v = u];
    }
}

四大操作實現

• Link(u,v)：MakeRoot(u); fa[u] = v; (先判斷連通性)。
• Cut(u,v)：MakeRoot(u); Splay(v); 斷開 ch[v][0] 與 fa[u]。
• Add(u,v,w)：Split(u,v); 對 ch[u][1] (v 方向子樹)、v (另一支)、u (LCA) 分別 add_val。
• Query(u,v)：Split(u,v); 取 max(ch[u][1], v, u)。

初始化建樹

輸入給定初始樹邊。DFS 建立父子關係 (fa[child] = parent)，再初始化 LCT 節點值。根節點 fa[1] = 0。

複雜度

• 單次操作：O(log N) 攤還 (Splay 特性)。
• 總計：O((N+Q) log N)。

關鍵細節

• rt[x] 標記虛/實邊：true 表示該邊為虛邊 (不在當前 Splay 中)。
• pushup 維護 max = max(val, max[left], max[right])。
• pushrev 交換左右子樹並翻轉 rev 標記。
• 判斷連通性：FindRoot(u) == FindRoot(v) (Access+Splay 後最左節點)。