POJ 3237 Tree：樹鏈剖分維護路徑最大值與翻轉

題目大意

給定一棵樹，邊有權值。支持三種操作：

• 修改某條邊的權值
• 查詢路徑上最大邊權
• 將路徑上所有邊權取反（乘 -1）

需用樹鏈剖分 + 線段樹維護，線段樹節點保存最大值、最小值、翻轉標記。

樹鏈剖分核心步驟

1. DFS1：計算 size[u]、son[u]（重兒子）、depth[u]、fa[u]。
2. DFS2：分配 dfn[u]（線段樹下標）、top[u]（重鏈頂點）、w[dfn[u]]（邊權映射到深度較深的節點）。

線段樹維護信息

• Max、Min：區間最大/最小值。
• lazy：翻轉標記（0/1）。
• PushDown 時：交換子節點 Max/Min，翻轉子節點 lazy 標記。
• PushUp：Max = max(lc.Max, rc.Max)，Min = min(lc.Min, rc.Min)。

關鍵操作實現

路徑查詢最大值

int queryPath(int u, int v) {
    int ans = -INF;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        ans = max(ans, segQuery(dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (u == v) return ans;
    if (depth[u] > depth[v]) swap(u, v);
    return max(ans, segQuery(dfn[u]+1, dfn[v])); // 邊權在深節點
}

路徑翻轉

void negatePath(int u, int v) {
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        segNegate(dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (u == v) return;
    if (depth[u] > depth[v]) swap(u, v);
    segNegate(dfn[u]+1, dfn[v]);
}

單點修改

void updateEdge(int u, int v, int val) {
    if (depth[u] > depth[v]) swap(u, v); // v 是深節點
    segUpdate(dfn[v], val);
}

完整代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
const int INF = 0x3f3f3f3f;

struct Edge { int to, w, next; } e[MAXN*2];
int head[MAXN], ecnt;
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rnk[MAXN], w[MAXN], tim;

void addEdge(int u, int v, int w) { ... }
void dfs1(int u, int f) { ... }
void dfs2(int u, int tp) { ... }

// 線段樹
struct SegNode { int mx, mn, lazy; } seg[MAXN*4];
void pushUp(int rt) { ... }
void pushDown(int rt) { ... }
void build(int rt, int l, int r) { ... }
void update(int rt, int l, int r, int pos, int val) { ... }
void negate(int rt, int l, int r, int L, int R) { ... }
int query(int rt, int l, int r, int L, int R) { ... }

// 主函數處理輸入、調用上述操作
int main() { ... }

難點與注意點

• 邊權映射到深度較深的節點，查詢/修改時注意 dfn[u]+1 排除 LCA 點。
• 翻轉操作需同時維護 Max 和 Min，PushDown 時交換兩者並傳遞標記。
• 初始化時 Max = -INF, Min = INF，避免未賦值節點干擾。

總結

POJ 3237 是樹鏈剖分 + 線段樹維護路徑信息的經典題目，包含區間翻轉（取反）操作，考驗對線段樹懶標記與 Max/Min 同步維護的理解。掌握重鏈剖分模板、線段樹懶標記設計、路徑拆解技巧，即可輕鬆應對。