您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

BZOJ 1036 樹鏈剖分入門詳解：重輕鏈分解、線段樹維護路徑查詢與修改

編輯：C++ 入門

樹鏈剖分核心概念

重兒子：節點 v 的子節點中子樹大小 size 最大者。
輕兒子：其他子節點。
重邊：連接節點與其重兒子的邊。
輕邊：連接節點與輕兒子的邊。
重鏈：由重邊連接而成的路徑。
輕鏈：單條輕邊（視為長度 1 的鏈）。

性質：從根到任意節點路徑上，輕邊數量 ≤ log n。故路徑可分解為 ≤ log n 段重鏈。

兩次 DFS 預處理


// 第一次 DFS：計算 size、depth、fa、son(重兒子)
void dfs1(int fa, int u, int dep) {
    fa[u] = fa; depth[u] = dep; size[u] = 1; son[u] = 0;
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v == fa) continue;
        dfs1(u, v, dep+1);
        if (size[v] > size[son[u]]) son[u] = v;
        size[u] += size[v];
    }
}

// 第二次 DFS：重鏈優先，分配 dfn 序(w)、鏈頂(top)
void dfs2(int topNode, int u) {
    w[u] = ++dfnCnt; rev[dfnCnt] = u; top[u] = topNode;
    if (son[u]) dfs2(topNode, son[u]);  // 重兒子繼承鏈頂
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v != fa[u] && v != son[u]) dfs2(v, v);  // 輕兒子自成鏈頂
    }
}

w[u] 為節點在線段樹中的位置，top[u] 為其所在重鏈的頂端節點。重鏈節點在 dfn 序中連續，便於區間操作。

線段樹維護路徑資訊

本題需支援：路徑最大值查詢、路徑和查詢、單點修改。


struct SegTree {
    int l, r, maxv, sum;
} tr[4*MAXN];

void pushup(int u) {
    tr[u].maxv = max(tr[u<<1].maxv, tr[u<<1|1].maxv);
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void build(int u, int l, int r) {
    tr[u].l = l; tr[u].r = r;
    if (l == r) { tr[u].maxv = tr[u].sum = val[rev[l]]; return; }
    int mid = (l+r)>>1;
    build(u<<1, l, mid); build(u<<1|1, mid+1, r);
    pushup(u);
}

void modify(int u, int pos, int v) {
    if (tr[u].l == tr[u].r) { tr[u].maxv = tr[u].sum = v; return; }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (pos <= mid) modify(u<<1, pos, v);
    else modify(u<<1|1, pos, v);
    pushup(u);
}

int queryMax(int u, int l, int r) {
    if (tr[u].l > r || tr[u].r < l) return -INF;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].maxv;
    return max(queryMax(u<<1, l, r), queryMax(u<<1|1, l, r));
}

int querySum(int u, int l, int r) {
    if (tr[u].l > r || tr[u].r < l) return 0;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    return querySum(u<<1, l, r) + querySum(u<<1|1, l, r);
}

路徑查詢與修改：跳鏈過程


// 路徑最大值
int queryPathMax(int x, int y) {
    int res = -INF;
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) swap(x, y);
        res = max(res, queryMax(1, w[top[x]], w[x]));
        x = fa[top[x]];
    }
    if (depth[x] > depth[y]) swap(x, y);
    res = max(res, queryMax(1, w[x], w[y]));
    return res;
}

// 路徑和
int queryPathSum(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) swap(x, y);
        res += querySum(1, w[top[x]], w[x]);
        x = fa[top[x]];
    }
    if (depth[x] > depth[y]) swap(x, y);
    res += querySum(1, w[x], w[y]);
    return res;
}

// 單點修改
void updateNode(int x, int v) { modify(1, w[x], v); }

關鍵：每次跳到深度較深的鏈頂，查詢該鏈段，再跳到鏈頂父節點。最終同鏈時直接查區間。

完整代碼


#include 
using namespace std;

const int MAXN = 123333;
const int INF = 0x3f3f3f3f;

int n, m, val[MAXN];
int head[MAXN], to[2*MAXN], nxt[2*MAXN], ecnt;
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN];
int top[MAXN], w[MAXN], rev[MAXN], dfnCnt;
int b[MAXN];  // dfn 序對應的值

struct SegTree { int l, r, maxv, sum; } tr[4*MAXN];

void addEdge(int u, int v) {
    to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
}

void dfs1(int u, int f) {
    fa[u] = f; dep[u] = dep[f] + 1; sz[u] = 1; son[u] = 0;
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v == f) continue;
        dfs1(v, u);
        if (sz[v] > sz[son[u]]) son[u] = v;
        sz[u] += sz[v];
    }
}

void dfs2(int u, int tp) {
    top[u] = tp; w[u] = ++dfnCnt; rev[dfnCnt] = u; b[dfnCnt] = val[u];
    if (son[u]) dfs2(son[u], tp);
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v != fa[u] && v != son[u]) dfs2(v, v);
    }
}

void pushup(int u) {
    tr[u].maxv = max(tr[u<<1].maxv, tr[u<<1|1].maxv);
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void build(int u, int l, int r) {
    tr[u].l = l; tr[u].r = r;
    if (l == r) { tr[u].maxv = tr[u].sum = b[l]; return; }
    int mid = (l+r)>>1;
    build(u<<1, l, mid); build(u<<1|1, mid+1, r);
    pushup(u);
}

void modify(int u, int pos, int v) {
    if (tr[u].l == tr[u].r) { tr[u].maxv = tr[u].sum = v; return; }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (pos <= mid) modify(u<<1, pos, v);
    else modify(u<<1|1, pos, v);
    pushup(u);
}

int queryMax(int u, int l, int r) {
    if (tr[u].l > r || tr[u].r < l) return -INF;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].maxv;
    return max(queryMax(u<<1, l, r), queryMax(u<<1|1, l, r));
}

int querySum(int u, int l, int r) {
    if (tr[u].l > r || tr[u].r < l) return 0;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    return querySum(u<<1, l, r) + querySum(u<<1|1, l, r);
}

int askMax(int x, int y) {
    int res = -INF;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res = max(res, queryMax(1, w[top[x]], w[x]));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    res = max(res, queryMax(1, w[x], w[y]));
    return res;
}

int askSum(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res += querySum(1, w[top[x]], w[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    res += querySum(1, w[x], w[y]);
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        addEdge(u, v); addEdge(v, u);
    }
    for (int i = 1; i <= n; ++i) scanf("%d", &val[i]);
    dfs1(1, 0); dfs2(1, 1);
    build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        char op[10]; int x, y; scanf("%s%d%d", op, &x, &y);
        if (op[0] == 'C') updateNode(x, y);
        else if (op[1] == 'M') printf("%d\n", askMax(x, y));
        else printf("%d\n", askSum(x, y));
    }
    return 0;
}