POJ 3237 Tree：鏈切樹處理邊權翻轉與路徑最大值查詢

問題背景

給定一棵擁有 N 個節點的樹，節點編號為 1 至 N，邊編號為 1 至 N−1，每條邊帶有權重。需支援以下三種操作：

• CHANGE i v：將第 i 條邊的權重修改為 v。
• NEGATE a b：將節點 a 到 b 路徑上所有邊的權重取反（乘以 −1）。
• QUERY a b：查詢節點 a 到 b 路徑上邊權的最大值。

輸入包含多組測試資料，每組以 DONE 結束。對每個 QUERY 輸出結果。

核心思路：Link-Cut Tree (LCT)

本題屬於動態樹問題，需支援路徑修改（翻轉）、單點修改（改邊權）與路徑查詢（最大值）。Link-Cut Tree 通過 Splay 樹維護偏好路徑，能在 O(log N) 平均時間內完成上述操作。

關鍵技術點

1. 邊權轉點權：將第 i 條邊的權重存儲在其深度較深的端點上，並記錄 belong[i] = v，方便 CHANGE 直接定位節點。
2. 翻轉標記：維護 neg[x] 標記，下推時交換 maxn 與 minn，並將 key[x] 取反；因為取反後最大值變為原最小值的相反數。
3. 路徑操作統一入口：access(y) 將 y 到根的路徑拉成一條右偏鏈，隨後從 x 向上跳轉，利用 bef[]（虛樹父節點）逐段 Splay，即可完成路徑區間的修改或查詢。

主要函數解析

void Not(int x) {           // 翻轉節點 x 的權值與子樹極值
    if (x) {
        neg[x] ^= 1;
        swap(minn[x], maxn[x]);
        key[x] = -key[x];
        minn[x] = -minn[x];
        maxn[x] = -maxn[x];
    }
}

int query(int x, int y) {   // 查詢 x-y 路徑最大邊權
    access(y);
    for (int y = 0; x; x = bef[x]) {
        splay(x);
        if (!bef[x]) return max(maxn[y], maxn[next[x][1]]);
        // 斷開右子樹並接入 y，繼續向上
    }
    return 0;
}

複雜度分析

每次操作均攤 O(log N)，空間 O(N)。N ≤ 10,000，測試案例 ≤ 20，極易在時限內通過。

完整 AC 代碼（C++）

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 0x7fffffff;
const int MAXN = 100050;

struct LCT {
    int bef[MAXN], pre[MAXN], next[MAXN][2];
    int key[MAXN], val[MAXN], belong[MAXN];
    int maxn[MAXN], minn[MAXN], neg[MAXN];

    void init() {
        memset(pre, 0, sizeof(pre));
        memset(next, 0, sizeof(next));
        memset(neg, 0, sizeof(neg));
        maxn[0] = -INF; minn[0] = INF;
    }
    void pushup(int x) {
        maxn[x] = minn[x] = key[x];
        if (next[x][0]) {
            maxn[x] = max(maxn[x], maxn[next[x][0]]);
            minn[x] = min(minn[x], minn[next[x][0]]);
        }
        if (next[x][1]) {
            maxn[x] = max(maxn[x], maxn[next[x][1]]);
            minn[x] = min(minn[x], minn[next[x][1]]);
        }
    }
    void Not(int x) {
        if (x) {
            neg[x] ^= 1;
            swap(minn[x], maxn[x]);
            key[x] = -key[x];
            minn[x] = -minn[x];
            maxn[x] = -maxn[x];
        }
    }
    void pushdown(int x) {
        if (neg[x]) {
            Not(next[x][0]); Not(next[x][1]);
            neg[x] = 0;
        }
    }
    void rotate(int x, int kind) {
        int y = pre[x], z = pre[y];
        pushdown(y); pushdown(x);
        next[y][!kind] = next[x][kind];
        pre[next[x][kind]] = y;
        next[z][next[z][1] == y] = x;
        pre[x] = z;
        next[x][kind] = y;
        pre[y] = x;
        pushup(y);
    }
    void splay(int x) {
        int rt;
        for (rt = x; pre[rt]; rt = pre[rt]);
        if (x != rt) { bef[x] = bef[rt]; bef[rt] = 0; }
        pushdown(x);
        while (pre[x]) {
            if (next[pre[x]][0] == x) rotate(x, 1);
            else rotate(x, 0);
        }
        pushup(x);
    }
    void access(int x) {
        for (int fa = 0; x; x = bef[x]) {
            splay(x); pushdown(x);
            pre[next[x][1]] = 0; bef[next[x][1]] = x;
            next[x][1] = fa; pre[fa] = x; bef[fa] = 0;
            fa = x; pushup(x);
        }
    }
    void change(int idx, int v) { // idx 為輸入邊編號（1-based）
        int t = belong[idx - 1];
        splay(t); key[t] = v; pushup(t);
    }
    void negate(int x, int y) {
        access(y);
        for (int y = 0; x; x = bef[x]) {
            splay(x);
            if (!bef[x]) { Not(y); Not(next[x][1]); return; }
            pushdown(x);
            pre[next[x][1]] = 0; bef[next[x][1]] = x;
            next[x][1] = y; pre[y] = x; bef[y] = 0;
            y = x; pushup(x);
        }
    }
    int query(int x, int y) {
        access(y);
        for (int y = 0; x; x = bef[x]) {
            splay(x);
            if (!bef[x]) return max(maxn[y], maxn[next[x][1]]);
            pushdown(x);
            pre[next[x][1]] = 0; bef[next[x][1]] = x;
            next[x][1] = y; pre[y] = x; bef[y] = 0;
            y = x; pushup(x);
        }
        return 0;
    }
} lct;

int head[MAXN], cnt;
struct Edge { int u, v, w, next; } edge[MAXN << 1];
void addEdge(int u, int v, int w) {
    edge[cnt] = {u, v, w, head[u]}; head[u] = cnt++;
}
void bfs(int root) {
    queue<int> q; memset(vis, 0, sizeof(vis));
    vis[root] = 1; q.push(root);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; ~i; i = edge[i].next) {
            int v = edge[i].v;
            if (!vis[v]) {
                lct.bef[v] = u;
                lct.key[v] = edge[i].w;
                lct.belong[i >> 1] = v;
                vis[v] = 1; q.push(v);
            }
        }
    }
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        memset(head, -1, sizeof(head)); cnt = 0;
        for (int i = 1; i < n; ++i) {
            int a, b, c; scanf("%d%d%d", &a, &b, &c);
            addEdge(a, b, c); addEdge(b, a, c);
        }
        lct.init(); bfs(1);
        char op[10];
        while (scanf("%s", op) && op[0] != 'D') {
            if (op[0] == 'Q') { // QUERY
                int a, b; scanf("%d%d", &a, &b);
                printf("%d\n", lct.query(a, b));
            } else if (op[0] == 'C') { // CHANGE
                int i, v; scanf("%d%d", &i, &v);
                lct.change(i, v);
            } else { // NEGATE
                int a, b; scanf("%d%d", &a, &b);
                lct.negate(a, b);
            }
        }
    }
    return 0;
}