BZOJ 3282 Tree：Link-Cut Tree 維護動態樹異或路徑查詢

問題描述

維護一棵動態森林，支持四種操作（節點數 ≤ 300000）：

1. Query x y：詢問路徑 x-y 上所有節點值的異或和
2. Link x y：連接 x, y（不保證原本不連通）
3. Cut x y：刪除邊 (x,y)（不保證原本連通）
4. Modify x v：將節點 x 的值改為 v

LCT 維護路徑異或和

每個節點存儲：

• val：自身值
• xor_sum：Splay 子樹（虛擬樹+實際子樹）的異或和
• rev：翻轉標記

pushup(x)：xor_sum = val ^ xor_sum[left] ^ xor_sum[right]。

核心操作實現

// 查詢路徑 x-y 異或和
int query(int x, int y) {
    makeroot(x);
    access(y); splay(y);
    return t[y].xor_sum;
}

// 修改節點值
void modify(int x, int v) {
    splay(x); // 先 splay 到輔助樹根
    t[x].val = v;
    pushup(x);
}

// 連接 x-y（若已連通則忽略）
void link(int x, int y) {
    if (findroot(x) == findroot(y)) return;
    makeroot(x);
    t[x].fa = y;
}

// 斷開 x-y（若不連通或非直接邊則忽略）
void cut(int x, int y) {
    if (x == y || findroot(x) != findroot(y)) return;
    makeroot(x);
    access(y); splay(y);
    if (t[y].ch[0] != x) return;
    t[y].ch[0] = t[x].fa = 0;
    pushup(y);
}

關鍵避坑點

• 不保證連通性：link 前必須 findroot 判斷；cut 前判斷連通且為直接邊。
• Modify 必須 Splay：直接修改 val 後需 pushup 更新祖先，但節點可能不在輔助樹根，故先 splay(x) 使其成為輔助樹根，再更新，祖先鏈會在後續 access 時自動維護。
• Query 順序：makeroot(x); access(y); splay(y); 使 y 的 Splay 樹恰好包含 x-y 路徑所有節點，xor_sum 即為答案。

完整代碼框架（關鍵部分）

const int MAXN = 300010;
struct Node { int val, xor_sum; bool rev; int ch[2], fa; } t[MAXN];

bool isroot(int x) { return t[t[x].fa].ch[0]!=x && t[t[x].fa].ch[1]!=x; }
void pushrev(int x) { if(x) { t[x].rev^=1; swap(t[x].ch[0], t[x].ch[1]); } }
void pushdown(int x) { if(t[x].rev) { pushrev(t[x].ch[0]); pushrev(t[x].ch[1]); t[x].rev=0; } }
void pushup(int x) { t[x].xor_sum = t[x].val ^ t[t[x].ch[0]].xor_sum ^ t[t[x].ch[1]].xor_sum; }

void rotate(int x) { ... }
void splay(int x) { ... } // 含 pushdown 路徑
void access(int x) { ... }
void makeroot(int x) { access(x); splay(x); pushrev(x); }
int findroot(int x) { access(x); splay(x); while(pushdown(x), t[x].ch[0]) x=t[x].ch[0]; splay(x); return x; }

// 主循環讀取操作分發

複雜度

均攤 O(log N) 每操作，總時間 O(Q log N) 滿足 30 萬操作限制。

總結

BZOJ 3282 是 LCT 維護路徑聚合信息（異或和）的標準題。在 BZOJ 2049（連通性）基礎上增加 val/xor_sum/pushup，並正確處理 Modify 時的 Splay 時機。掌握「makeroot + access + splay」暴露路徑的核心模式，可輕鬆擴展到路徑求和/最大值/矩陣乘積等聚合查詢。