學(xué)習(xí)樹(shù)鏈剖分我看過(guò)以下博客：
樹(shù)鏈剖分原理和實(shí)現(xiàn)
樹(shù)鏈剖分整理總結(jié)

知道大概之后，我以為要多加深記憶的地方：
對(duì)于每一個(gè)重兒子，其top必然是其父親的top，并且由于要用其它數(shù)據(jù)結(jié)構(gòu)（如樹(shù)狀數(shù)組，線段樹(shù)）等來(lái)維護(hù)，所以一條鏈在物理上存儲(chǔ)是連續(xù)的。
那么如何連續(xù)起來(lái)？其實(shí)靠的是dfs1打的標(biāo)記，一條重鏈的dfs序號(hào)必然連續(xù)。

了解這個(gè)之后，求u到v之間的某些數(shù)值，就可以更好地理解那些輔助的數(shù)據(jù)結(jié)構(gòu)是如何操縱值的了。比如在樹(shù)狀數(shù)組中區(qū)間是[a,b]，那么要把[a，b]的值增加k，相當(dāng)于add(a,k)，add(b+1,-k)。
參考kuangbin的模板，假設(shè)是基于點(diǎn)權(quán)，查詢單點(diǎn)值，修改路徑上的點(diǎn)權(quán)（HDU 3966 樹(shù)鏈剖分+樹(shù)狀數(shù)組）

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 5e4 + 5;

struct Edge {
    int to, next;
} edge[maxN * 2];

int head[maxN], tot;
int top[maxN];  // top[v]即v所在重鏈的頂端結(jié)點(diǎn)
int fa[maxN];   // 父節(jié)點(diǎn)
int deep[maxN]; // 深度
int num[maxN];  // num[v] 以v為根的子樹(shù)結(jié)點(diǎn)數(shù)
int p[maxN];    // p[v]為v的dfs位置
int fp[maxN];   // 與p相反
int son[maxN];  // 重子編號(hào)
int pos;

void init() {
    tot = 0;
    // 使用bit 編號(hào)從1開(kāi)始
    pos = 1;
    mst(head, -1);
    mst(son, -1);
}

void addEdge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs1(int u, int pre, int d) {
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != pre) {
            dfs1(v, u, d + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[v] > num[son[u]])
                son[u] = v;
        }
    }
}

void getPos(int u, int sp) {
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if (son[u] == -1)
        return;
    getPos(son[u], sp);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u])
            getPos(v, v);
    }
}

int bit[maxN];
int n;
int sum(int i) {
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}
int add(int i, int x) {
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}

void modify(int u, int v, int val) {
    int f1 = top[u], f2 = top[v];
    int tmp = 0;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        add(p[f1], val);
        add(p[u] + 1, -val);
        u = fa[f1];
        f1 = top[u];
    }
    if (deep[u] > deep[v])
        swap(u, v);
    add(p[u], val);
    add(p[v] + 1, -val);
}

int a[maxN];
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    int M, P;
    while (~scanf("%d%d%d", &n, &M, &P)) {
        int u, v;
        int C1, C2, K;
        char op[10];
        init();
        rep(i, 1, n + 1)
            scanf("%d", &a[i]);

        while (M--) {
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }

        dfs1(1, 0, 0);
        getPos(1, 1);
        mst(bit, 0);

        rep(i, 1, n + 1) {
            add(p[i], a[i]);
            add(p[i] + 1, -a[i]);
        }

        while (P--) {
            scanf("%s", op);
            if (op[0] == 'Q') {
                scanf("%d", &u);
                printf("%d\n", sum(p[u]));
            } else {
                scanf("%d%d%d", &C1, &C2, &K);
                if (op[0] == 'D')
                    K = -K;
                modify(C1, C2, K);
            }
        }
    }
    return 0;
}

基于邊權(quán)，修改單條邊權(quán)，查詢路徑邊權(quán)最大值（SPOJ QTREE 樹(shù)鏈剖分+線段樹(shù)）
那么，如何解決邊權(quán)的計(jì)算問(wèn)題呢？我們可以把邊看作點(diǎn)。留意到樹(shù)中節(jié)點(diǎn)可以有多條出邊，但入邊最多只有一條。故而我們可以拿點(diǎn)的序號(hào)來(lái)唯一表示邊。
先根據(jù)點(diǎn)的關(guān)系完成樹(shù)鏈剖分的工作。接著我們根據(jù)邊在樹(shù)鏈剖分時(shí)的序號(hào)（即dfs序號(hào)）操縱線段樹(shù)即可。我想表達(dá)的是，線段樹(shù)中的區(qū)間序號(hào)只與dfs1序號(hào)有關(guān)，它是不需明白點(diǎn)和邊的意義的，這里不必想得復(fù)雜。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e4 + 5;
int N, M, T;

// 線段樹(shù) 
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int seg[maxN << 2];
void push_up(int rt) { seg[rt] = max(seg[rt << 1], seg[rt << 1 | 1]); }
void build(int l, int r, int rt) {
    seg[rt] = 0;
    if (l == r) return;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
}
int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R)
        return seg[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret = max(ret, query(L, R, lson));
    if (R > m) ret = max(ret, query(L, R, rson));
    return ret;
}
void update(int p, int x, int l, int r, int rt) {
    if (l == r) {
        seg[rt] = x;
        return;
    }
    int m = (r + l) >> 1;
    if (p <= m) update(p, x, lson);
    else update(p, x, rson);
    push_up(rt);
}

// 樹(shù)鏈剖分
struct Edge {
    int to, next;
} edge[maxN * 2];

int head[maxN], tot;
int top[maxN];  // top[v]即v所在重鏈的頂端結(jié)點(diǎn)
int fa[maxN];   // 父節(jié)點(diǎn)
int deep[maxN]; // 深度
int num[maxN];  // num[v] 以v為根的子樹(shù)結(jié)點(diǎn)數(shù)
int p[maxN];    // p[v]為v的dfs位置
int fp[maxN];   // 與p相反
int son[maxN];  // 重子編號(hào)
int pos;

void init() {
    tot = 0;
    pos = 0;
    mst(head, -1);
    mst(son, -1);
}

void addEdge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs1(int u, int pre, int d) {
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != pre) {
            dfs1(v, u, d + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[v] > num[son[u]])
                son[u] = v;
        }
    }
}

void getPos(int u, int sp) {
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if (son[u] == -1)
        return;
    getPos(son[u], sp);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u])
            getPos(v, v);
    }
}

// 查詢u->v邊的max
int findMax(int u, int v) {
    int f1 = top[u], f2 = top[v];
    int tmp = 0;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        tmp = max(tmp, query(p[f1], p[u], 0, pos - 1, 1));
        u = fa[f1];
        f1 = top[u];
    }
    if (u == v) return tmp;
    if (deep[u] > deep[v]) swap(u, v);
    return max(tmp, query(p[son[u]], p[v], 0, pos - 1, 1));
}

int e[maxN][3];

// CHANGE i ti 修改第i條邊的值為ti
// QUERY a b 詢問(wèn)a到b的最大邊權(quán)
// DONE 結(jié)束符號(hào)
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d", &N);
        rep(i, 0, N - 1) {
            scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
            addEdge(e[i][0], e[i][1]);
            addEdge(e[i][1], e[i][0]);
        }
        dfs1(1, 0, 0);
        getPos(1, 1);
        build(0, pos - 1, 1);

        rep(i, 0, N - 1) {
            if (deep[e[i][0]] > deep[e[i][1]])
                swap(e[i][0], e[i][1]);
            update(p[e[i][1]], e[i][2], 0, pos - 1, 1);
        }
        char op[10];
        int u, v;
        while (~scanf("%s", op)) {
            if (op[0] == 'D') break;
            scanf("%d %d", &u, &v);
            if (op[0] == 'C')
                update(p[e[u - 1][1]], v, 0, pos - 1, 1);
            else
                printf("%d\n", findMax(u, v));
        }
    }
    return 0;
}

bzoj 1036 修改點(diǎn)權(quán)，問(wèn)u，v路徑上的點(diǎn)權(quán)之和，點(diǎn)權(quán)最大值

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 3e4 + 5;
int N, M, T;


// 線段樹(shù)
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int big[maxN << 2], sum[maxN << 2];
void push_up(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    big[rt] = max(big[rt << 1], big[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
    big[rt] = -inf;
    sum[rt] = 0;
    if (l == r)
        return;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int p, int to, int l, int r, int rt) {
    if (l == r) {
        sum[rt] = to;
        big[rt] = to;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p, to, lson);
    else if (p > m) update(p, to, rson);
    push_up(rt);
}
// mode 1求和 2求最大值
int query(int L, int R, int l, int r, int rt, int mode) {
    if (L <= l && r <= R) {
        if (mode == 1) return sum[rt];
        else return big[rt];
    }
    int m = (l + r) >> 1;
    if (mode == 1) {
        int ret = 0;
        if (L <= m) ret += query(L, R, lson, 1);
        if (R > m) ret += query(L, R, rson, 1);
        return ret;
    } else {
        int ret = -inf * 2;
        if (L <= m) ret = max(ret, query(L, R, lson, 2));
        if (R > m) ret = max(ret, query(L, R, rson, 2));
        return ret;
    }
}

// 點(diǎn)權(quán) 樹(shù)鏈剖分
struct Edge { int to, next; } edge[maxN * 2];
int head[maxN], tot;
int top[maxN];
int fa[maxN];
int deep[maxN];
int num[maxN];
int p[maxN];
int fp[maxN];
int son[maxN];
int pos;

void init() { tot = 0; pos = 1; mst(head, -1); mst(son, -1); }
void addEdge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dfs1(int u, int pre, int d) {
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v == pre) continue;
        dfs1(v, u, d + 1);
        num[u] += num[v];
        if (son[u] == -1 || num[v] > num[son[u]])
            son[u] = v;
    }
}
void getPos(int u, int sp) {
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if (son[u] == -1) return;
    getPos(son[u], sp);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u])
            getPos(v, v);
    }
}

int getMax(int u, int v) {
    int f1 = top[u], f2 = top[v];
    int tmp = -inf;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        tmp = max(tmp, query(p[f1], p[u], 1, N, 1, 2));
        u = fa[f1], f1 = top[u];
    }
    if (deep[u] > deep[v]) swap(u, v);
    return max(tmp, query(p[u], p[v], 1, N, 1, 2));
}
int getSum(int u, int v) {
    int f1 = top[u], f2 = top[v];
    int s = 0;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        s += query(p[f1], p[u], 1, N, 1, 1);
        u = fa[f1], f1 = top[u];
    }
    if (deep[u] > deep[v]) swap(u, v);
    return s += query(p[u], p[v], 1, N, 1, 1);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    scanf("%d", &N);
    init();
    int u, v;
    rep(i, 0, N - 1) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    dfs1(1, 0, 0);
    getPos(1, 1);
    build(1, N, 1);
    int w;
    rep(i, 1, N + 1) {
        scanf("%d", &w);
        update(p[i], w, 1, N, 1);
    }
    scanf("%d", &T);
    char op[10];
    while (T--) {
        scanf("%s %d %d", op, &u, &v);
        if (op[1] == 'M')
            printf("%d\n", getMax(u, v));
        else if (op[1] == 'S')
            printf("%d\n", getSum(u, v));
        else
            update(p[u], v, 1, N, 1);
    }
    return 0;
}