树链剖分模板

树链剖分（点权）模板

int n, cnt, head[maxn], tim;
int dep[maxn], siz[maxn], fa[maxn];
int son[maxn], top[maxn], a[maxn];
int tid[maxn], out[maxn], pos[maxn];
struct node {
    int to, next, w;
}e[maxn<<1];
void add(int u, int v, int w) {
    e[cnt] = {v, head[u], w};
    head[u] = cnt++;
}
void init() {
   cnt = 0; for(int i = 1; i <= n; i++) son[i] = head[i] = -1;
    tim = 0;
}
void dfs1(int u, int f, int deep) {
    dep[u] = deep + 1; siz[u] = 1;
    for (int i = head[u] ; ~i ; i = e[i].next) {
        int to = e[i].to;
        if (to == f) continue;
        fa[to] = u;
        dfs1(to, u, deep+1);
        siz[u] += siz[to];
        if (son[u] == -1 || siz[to] > siz[son[u]]) {
            son[u] = to;
        }
    }
}
void dfs2(int u, int tp) {
    top[u] = tp;
    tid[u] = ++tim;
    pos[tim] = u;
    if (son[u] == -1) {
        out[u] = tim;
        return ;
    }
    dfs2(son[u], tp);
    for (int i = head[u] ; ~i ; i = e[i].next) {
        int to = e[i].to;
        if (to != son[u] && to != fa[u]) {
            dfs2(to, to);
        }
    }
    out[u] = tim;
}
ll get_sum(int x, int y) {//求路径和
    ll ans = 0;
    for (;top[x] != top[y] ; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query_sum(1, tid[top[x]], tid[x]);
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans += query_sum(1, tid[x], tid[y]);
    return ans;
}
ll get_max(int x, int y) {//区间最值
    ll mx = -inf;
    for (;top[x] != top[y] ; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        mx = max(mx, query_max(1, tid[top[x]], tid[x]));
    }
    if (dep[x] > dep[y]) swap(x, y);
    mx = max(mx, query_max(1, tid[x], tid[y]));
    return mx;
}
void add_val(int x, int y, ll val) {//区间加
    for (;top[x] != top[y] ; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update(1, tid[top[x]], tid[x], val);
    }
    if (dep[x] > dep[y]) swap(x, y);
    update(1, tid[x], tid[y], val);
}
int get_lca(int x, int y) {//lca
    for (;top[x] != top[y]; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
    }
    if (dep[x] > dep[y]) swap(x, y);
    return x;
}

边权模板

int id[maxn], out[maxn], pos[maxn];
int n, m, cnt,  tim;
int siz[maxn], top[maxn];
int son[maxn], dep[maxn], fa[maxn];
int dd[maxn], dis[maxn], head[maxn];
struct node {
    int to, next, w, idx;
}e[maxn<<1];
void add(int u, int v, int w, int id) {
    e[cnt] = node{v, head[u], w, id};
    head[u] = cnt++;
}
void init() {
    cnt = 0; for(int i = 1; i <= n; i++) son[i] = head[i] = -1;
    tim = 0;
}
void dfs1(int u, int f, int deep) {
    dep[u] = deep + 1; siz[u] = 1;
    for (int i = head[u] ; ~i ; i = e[i].next) {
        int to = e[i].to;
        if (to == f) continue;
        fa[to] = u;
        dd[e[i].idx] = to;
        dfs1(to, u, deep+1);
        siz[u] += siz[to];
        if (son[u] == -1 || siz[to] > siz[son[u]]) {
            son[u] = to;
        }
    }
}
void dfs2(int u, int tp) {
    top[u] = tp;
    id[u] = ++tim;
    pos[tim] = u;
    if (son[u] == -1) {
        out[u] = tim;
        return ;
    }
    dfs2(son[u], tp);
    for (int i = head[u] ; ~i ; i = e[i].next) {
        int to = e[i].to;
        if (to != son[u] && to != fa[u]) {
            dfs2(to, to);
        }
    }
    out[u] = tim;
}
ll get_sum(int x, int y) {
    ll ans = 0;
    for (;top[x] != top[y] ; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query_sum(1, id[top[x]], id[x]);
    }
    if (dep[x] == dep[y]) return ans;
    if (dep[x] > dep[y]) swap(x, y);
    if (id[son[x]] > id[y]) swap(x, y);
    ans += query_sum(1, id[son[x]], id[y]);
    return ans;
}
ll get_max(int x, int y) {
    ll mx = -(1ll<<60);
    for (;top[x] != top[y] ; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        mx = max(mx, query_max(1, id[top[x]], id[x]));
    }
    if (dep[x] == dep[y]) return mx;
    if (dep[x] > dep[y]) swap(x, y);
    if (id[son[x]] > id[y]) swap(x, y);
    mx = max(mx, query_max(1, id[son[x]], id[y]));
    return mx;
}

ll val[maxn];
void solve(){
    scanf("%d", &n);init();
    for(int i = 1; i < n;  i++) {
    	int x, y, w;scanf("%d%d%d", &x, &y, &w);
    	add(x, y, w, i);add(y, x, w, i);
    	val[i] = 1ll*w;
    }
    dfs1(1, -1, 0);dfs2(1, 1);
    for(int i = 1; i < n; i++) a[dd[i]] = val[i];
    build(1, 1, n);
	char op[9];
    for(;scanf("%s", op) == 1 && op[0] != 'D';) {
    	int x, y;scanf("%d%d", &x, &y);
    	if(op[0] == 'C') update(1, id[dd[x]], id[dd[x]], y);
    	else printf("%lld\n", get_max(x, y));
    }
}

抄xdd的嘻嘻