To boldly go where no one has gone before.

【学习笔记】树链剖分

2019-03-13 23:26:15


树链剖分,就是指把树给剖成链,然后用数据结构进行树上的区间操作。

比如在这份笔记中,使用树链剖分+线段树维护(P3384)。

定义:一个节点$u$所有儿子中拥有子节点最多的儿子$v$就是重儿子,由$u$到$v$这条链就是重链。找到所有的重链后,就把树按照重儿子在前,轻儿子按照 dfn 的顺序投影到数据结构上的话,那么这棵树就变得类似一个区间了,维护起来也方便很多。

树链剖分

树链剖分要用到两次 dfs 。

第一次

第一次 dfs 需要记录父亲、深度、子树大小等信息,并且按照儿子的子树大小顺序找到重儿子

注意! 在更新重儿子的时候,千万要写$size[v] > size[son[u]]$,否则找到的根本就不是重儿子,整份代码也就是个假的树链剖分,当时就是因为这个地方写飘了,导致 TLE 了三个点。

inline void dfs1(int u, int fa) {
    f[u] = fa, depth[u] = depth[fa] + 1;
    size[u] = 1;
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == fa)
            continue;
        dfs1(v, u);
        size[u] += size[v];
        if(size[v] > size[son[u]]) //attention!
            son[u] = v;
    }
    return;
}

第二次

第二次 dfs 则就是拆树过程。先记录当前节点所在链的头节点$top[u]$(方便 LCA ),并且记录 dfn 序。注意:这里的 dfn 序则就是当前节点在新树中对应的新编号,线段树也是对这东西进行维护。但是为了方便访问,也要记录下 dfn 所对应的原数字编号$rev[cnt]$。此后,优先将当前链向下延展,然后对于所有轻儿子进行 dfs 。

inline void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++cnt;
    rev[cnt] = u;
    if(!son[u])
        return;
    dfs2(son[u], t);
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == f[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
    return;
}

数据结构维护

线段树维护不必多说,不过建树的时候注意当$l=r$的时候,要用原数值,即$v(num) = array[rev[l]]$,否则就$gg$了。

inline void build_tree(int l, int r, int num) {
    tag(num) = 0;
    l(num) = l, r(num) = r;
    if(l == r) {
        v(num) = array[rev[l]] % p;
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(l, mid, num<<1);
    build_tree(mid+1, r, num<<1|1);
    v(num) = (v(num<<1) + v(num<<1|1)) % p;
    return;
}

树上修改及查询

在原树上进行操作,等价于在$[u,v]$最短路中所有被包含的链进行操作。由于链被分成了一段一段的,想要精确找到这些链则是个难题。

这里用了 LCA ,不过不是倍增 LCA 。由于之前已经记录下来了父亲$f[u]$以及所在链的链头$top[u]$,所以根本不需要倍增,直接逮着开跑就行。

左右两侧节点的处理方式完全一致,以$x$节点的处理为例:

维护一个$\_x$表示当前$x$节点所在链的链头,当前处理的区间也就是$[dfn[\_x],dfn[x]]$。如果这个链头的深度比$\_y$大,说明这条链在$y$那条链下面,所以可以直接对当前区间进行数据结构操作,然后把$x$跳到$\_x$的父亲,再把$\_x$更新为新的$x$所对应的链头。

但这样子处理有个问题,那就是当$\_x$与$\_y$相同后,$x$与$y$不见得相同。因此在$while$循环外还要再进行一次维护,直接对$dfn[x]$与$dfn[y]$之间的区间进行操作即可。

这个样子就完成了树上操作,查询区间和以及修改区间都可以用这个方法实现。

inline long long summary(int &x, int &y) {
    long long sum = 0;
    int _x = top[x], _y = top[y];
    while(_x != _y) {
        if(depth[_x] >= depth[_y]) {
            sum = (sum + query(dfn[_x], dfn[x], 1)) % p;
            x = f[_x], _x = top[x];
        }
        else {
            sum = (sum + query(dfn[_y], dfn[y], 1)) % p;
            y = f[_y], _y = top[y];
        }
    }
    if(dfn[x] <= dfn[y])
        sum = (sum + query(dfn[x], dfn[y], 1)) % p;
    else
        sum = (sum + query(dfn[y], dfn[x], 1)) % p;
    return sum;
}

inline void update(int &x, int &y, long long c) {
    int _x = top[x], _y = top[y];
    while(_x != _y) {
        if(depth[_x] >= depth[_y]) {
            edit_tree(dfn[_x], dfn[x], 1, c);
            x = f[_x], _x = top[x];
        }
        else {
            edit_tree(dfn[_y], dfn[y], 1, c);
            y = f[_y], _y = top[y];
        }
    }
    if(dfn[x] <= dfn[y])
        edit_tree(dfn[x], dfn[y], 1, c);
    else
        edit_tree(dfn[y], dfn[x], 1, c);
    return;
}

主程序

主程序里头先$dfs1$,再从$root$进行$dfs2$,最后建树即可。

int main() {
    dfs1(r, 0);
    dfs2(r, r);
    build_tree(1, n, 1);
}

完整代码:

#include<bits/stdc++.h>
#define l(x) segtree[x].l
#define r(x) segtree[x].r
#define v(x) segtree[x].val
#define tag(x) segtree[x].tag
using namespace std;

const int MAXN = 100010;

struct EDGE {
    int to, next;
} edge[MAXN << 1];
int last[MAXN], id = 0;

struct SEGTREE {
    long long l, r, val, tag;
} segtree[MAXN*4];
long long array[MAXN];
int f[MAXN], depth[MAXN], son[MAXN], size[MAXN];
int top[MAXN], rev[MAXN], dfn[MAXN], cnt = 0;
int n, m, p, r, a, b, opt;
long long k;

//树链剖分过程 

inline void build_edge(int u, int v) {
    edge[++id].to = v;
    edge[id].next = last[u];
    last[u] = id;
    return;
}

inline void dfs1(int u, int fa) {
    f[u] = fa, depth[u] = depth[fa] + 1;
    size[u] = 1;
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == fa)
            continue;
        dfs1(v, u);
        size[u] += size[v];
        if(size[v] > size[son[u]]) //attention!
            son[u] = v;
    }
    return;
}

inline void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++cnt;
    rev[cnt] = u;
    if(!son[u])
        return;
    dfs2(son[u], t);
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == f[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
    return;
}

//线段树维护 

inline void build_tree(int l, int r, int num) {
    tag(num) = 0;
    l(num) = l, r(num) = r;
    if(l == r) {
        v(num) = array[rev[l]] % p;
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(l, mid, num<<1);
    build_tree(mid+1, r, num<<1|1);
    v(num) = (v(num<<1) + v(num<<1|1)) % p;
    return;
}

inline void pushdown(int num) {
    if(!tag(num))
        return;
    v(num<<1) = (v(num<<1) + tag(num) * (r(num<<1) - l(num<<1) + 1)) % p;
    v(num<<1|1) = (v(num<<1|1) + tag(num) * (r(num<<1|1) - l(num<<1|1) + 1)) % p;
    tag(num<<1) = (tag(num<<1) + tag(num)) % p;
    tag(num<<1|1) = (tag(num<<1|1) + tag(num)) % p;
    tag(num) = 0;
    return;
}

inline void edit_tree(int l, int r, int num, long long c) {
    if(l <= l(num) && r(num) <= r) {
        v(num) = (v(num) + c * (r(num) - l(num) + 1)) % p;
        tag(num) = (tag(num) + c) % p;
        return;
    }
    pushdown(num);
    int mid = (l(num) + r(num)) >> 1;
    if(l <= mid)
        edit_tree(l, r, num<<1, c);
    if(r > mid)
        edit_tree(l, r, num<<1|1, c);
    v(num) = (v(num<<1) + v(num<<1|1)) % p;
    return;
}

inline long long query(int l, int r, int num) {
    if(l <= l(num) && r(num) <= r)
        return v(num);
    pushdown(num);
    int mid = (l(num) + r(num)) >> 1;
    long long sum = 0;
    if(l <= mid)
        sum = (sum + query(l, r, num<<1)) % p;
    if(r > mid)
        sum = (sum + query(l, r, num<<1|1)) % p;
    return sum;
}

inline long long summary(int &x, int &y) {
    long long sum = 0;
    int _x = top[x], _y = top[y];
    while(_x != _y) {
        if(depth[_x] >= depth[_y]) {
            sum = (sum + query(dfn[_x], dfn[x], 1)) % p;
            x = f[_x], _x = top[x];
        }
        else {
            sum = (sum + query(dfn[_y], dfn[y], 1)) % p;
            y = f[_y], _y = top[y];
        }
    }
    if(dfn[x] <= dfn[y])
        sum = (sum + query(dfn[x], dfn[y], 1)) % p;
    else
        sum = (sum + query(dfn[y], dfn[x], 1)) % p;
    return sum;
}

inline void update(int &x, int &y, long long c) {
    int _x = top[x], _y = top[y];
    while(_x != _y) {
        if(depth[_x] >= depth[_y]) {
            edit_tree(dfn[_x], dfn[x], 1, c);
            x = f[_x], _x = top[x];
        }
        else {
            edit_tree(dfn[_y], dfn[y], 1, c);
            y = f[_y], _y = top[y];
        }
    }
    if(dfn[x] <= dfn[y])
        edit_tree(dfn[x], dfn[y], 1, c);
    else
        edit_tree(dfn[y], dfn[x], 1, c);
    return;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &r, &p);
    for(register int i = 1; i <= n; i++) {
        scanf("%lli", &array[i]);
        array[i] %= p;
    }
    for(register int i = 1; i < n; i++) {
        scanf("%d%d", &a, &b);
        build_edge(a, b);
        build_edge(b, a);
    }
    dfs1(r, 0);
    dfs2(r, r);
    build_tree(1, n, 1);
    for(register int i = 1; i <= m; i++) {
        scanf("%d", &opt);
        switch(opt) {
            case 1: {
                scanf("%d%d%lli", &a, &b, &k);
                update(a, b, k);
                break;
            }
            case 2: {
                scanf("%d%d", &a, &b);
                printf("%lli\n", summary(a, b));
                break;
            }
            case 3: {
                scanf("%d%lli", &a, &k);
                edit_tree(dfn[a], dfn[a]+size[a]-1, 1, k);
                break;
            }
            case 4: {
                scanf("%d", &a);
                printf("%lli\n", query(dfn[a], dfn[a]+size[a]-1, 1));
                break;
            }
        }
    }
    return 0;
}

如何用树链剖分+线段树维护树上路径颜色段数量呢?这里记录下一个骚气的做法,线段树还可以这样用!

一道比较好的树剖题 P2146

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

const int MAXN = 100010;
int fa[MAXN], depth[MAXN], dfn[MAXN], rev[MAXN];
int top[MAXN], size[MAXN], son[MAXN], cnt = 0;
int n, q;

struct SEGTREE {
    int l, r, len;
    long long tag, v;
} tree[MAXN << 2];
struct EDGE {
    int to, next;
} edge[MAXN << 1];
int id = 0, last[MAXN];

inline int read() {
    int res = 0, uz = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')
            uz = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        res = (res << 3) + (res << 1) + (ch ^ '0');
        ch = getchar();
    }
    return res * uz;
}

inline void build_edge(int u, int v) {
    edge[++id].to = v;
    edge[id].next = last[u];
    last[u] = id;
    return;
}

inline void dfs1(int u, int father) {
    fa[u] = father, depth[u] = depth[father] + 1;
    size[u] = 1;
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == father)
            continue;
        dfs1(v, u);
        size[u] += size[v];
        if(size[v] > size[son[u]])
            son[u] = v;
    }
    return;
}

inline void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++cnt;
    rev[cnt] = u;
    if(!son[u])
        return;
    dfs2(son[u], t);
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
    return;
}

inline void pushdown(int x) {
    if(!~tree[x].tag)
        return;
    tree[x<<1].v = tree[x].tag * tree[x<<1].len;
    tree[x<<1|1].v = tree[x].tag * tree[x<<1|1].len;
    tree[x<<1].tag = tree[x<<1|1].tag = tree[x].tag;
    tree[x].tag = -1;
    return;
}

inline void build_tree(int x, int l, int r) {
    tree[x].len = r - l + 1;
    tree[x].tag = -1, tree[x].v = 0;
    tree[x].l = l, tree[x].r = r;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build_tree(x<<1, l, mid);
    build_tree(x<<1|1, mid+1, r);
    return;
}

inline long long query(int l, int r, int x) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r)
        return tree[x].v;
    pushdown(x);
    int mid = (ll + rr) >> 1;
    long long res = 0;
    if(l <= mid)
        res += query(l, r, x<<1);
    if(r > mid)
        res += query(l, r, x<<1|1);
    return res;
}

inline void edit_tree(int l, int r, int x, int v) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r) {
        tree[x].v = v * tree[x].len;
        tree[x].tag = v;
        return;
    }
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        edit_tree(l, r, x<<1, v);
    if(r > mid)
        edit_tree(l, r, x<<1|1, v);
    tree[x].v = tree[x<<1].v + tree[x<<1|1].v;
    return;
}

inline void update(int u, int v, int val) {
    while(top[u] != top[v]) {
        if(depth[top[u]] < depth[top[v]])
            swap(u, v);
        edit_tree(dfn[top[u]], dfn[u], 1, val);
        u = fa[top[u]];
    }
    if(dfn[u] > dfn[v])
        swap(u, v);
    edit_tree(dfn[u], dfn[v], 1, val);
    return;
}

int main() {
    n = read();
    for(register int i = 2; i <= n; i++) {
        int depend = read() + 1;
        build_edge(depend, i);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    build_tree(1, 1, cnt);
    char s[20];
    q = read();
    while(q--) {
        scanf("%s", s);
        int app = read() + 1;
        int pre = tree[1].v;
        if(s[0] == 'i') {
            update(1, app, 1);
            printf("%lli\n", abs(tree[1].v - pre));
        }
        if(s[0] == 'u') {
            edit_tree(dfn[app], dfn[app] + size[app] - 1, 1, 0);
            printf("%lli\n", abs(tree[1].v - pre));
        }
    }
    return 0;
}

还有类似对边权处理、对区间取相反数的问题,都可以用树链剖分解决,可以把边权全部投影到后向点(边两端深度最大的点)上,处理一段路径的时候注意不能把 LCA 给处理了,否则直接$gg$

另外,取相反数的$lazytag$在下放、修改时有注意事项,相当于是$tree[x].tag\otimes1\,($取异或$)$,具体直接看代码。

例题 P1505

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

const int MAXN = 1000010;
const int INF = 1 << 30;

struct EDGE {
    int to, next, val;
} edge[MAXN << 1];
int last[MAXN], id = 0;
struct SEGTREE {
    int l, r, tag;
    int v, max, min;
} tree[MAXN << 2];

inline int read() {
    int res = 0, uz = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-')
            uz = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        res = (res << 3) + (res << 1) + (ch ^ '0');
        ch = getchar();
    }
    return res * uz;
}

inline void build_edge(int u, int v, int val) {
    edge[++id].to = v;
    edge[id].val = val;
    edge[id].next = last[u];
    last[u] = id;
    return;
}

int w[MAXN];
int size[MAXN], son[MAXN], depth[MAXN], fa[MAXN];
int top[MAXN], dfn[MAXN], rev[MAXN], cnt = 0;
int n;

inline void dfs1(int u, int father) {
    fa[u] = father, depth[u] = depth[father] + 1;
    size[u] = 1;
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == father)
            continue;
        w[v] = edge[i].val;
        dfs1(v, u);
        size[u] += size[v];
        if(size[v] > size[son[u]])
            son[u] = v;
    }
    return;
}

inline void dfs2(int u, int t) {
    dfn[u] = ++cnt, rev[cnt] = u;
    top[u] = t;
    if(!son[u])
        return;
    dfs2(son[u], t);
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
    return;
}

inline void pushdown(int x) {
    if(!tree[x].tag)
        return;
    //left
    tree[x<<1].tag += tree[x].tag;
    tree[x<<1].tag %= 2; //^=1
    tree[x<<1].v *= -1;
    swap(tree[x<<1].max, tree[x<<1].min);
    tree[x<<1].max *= -1, tree[x<<1].min *= -1;
    //right
    tree[x<<1|1].tag += tree[x].tag;
    tree[x<<1|1].tag %= 2; //^=1
    tree[x<<1|1].v *= -1;
    swap(tree[x<<1|1].max, tree[x<<1|1].min);
    tree[x<<1|1].max *= -1, tree[x<<1|1].min *= -1;
    tree[x].tag = 0;
    return;
}

inline void pushup(int x) {
    tree[x].v = tree[x<<1].v + tree[x<<1|1].v;
    tree[x].max = max(tree[x<<1].max, tree[x<<1|1].max);
    tree[x].min = min(tree[x<<1].min, tree[x<<1|1].min);
    return;
}

inline void build_tree(int x, int l, int r) {
    //printf("build %d->[%d,%d]\n", x, l, r);
    tree[x].l = l, tree[x].r = r;
    tree[x].tag = 0;
    if(l == r) {
        tree[x].v = tree[x].max = tree[x].min = w[rev[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(x<<1, l, mid);
    build_tree(x<<1|1, mid+1, r);
    pushup(x);
    return;
}

inline void edit_tree(int x, int p, int c) {
    //printf("edit_tree p:%d now:%d->[%d,%d]->%d\n", p, x, tree[x].l, tree[x].r, c);
    if(tree[x].l == tree[x].r) {
        tree[x].v = tree[x].max = tree[x].min = c;
        return;
    }
    pushdown(x);
    int mid = (tree[x].l + tree[x].r) >> 1;
    if(p <= mid)
        edit_tree(x<<1, p, c);
    else
        edit_tree(x<<1|1, p, c);
    pushup(x);
    return;
}

inline void reverse_tree(int x, int l, int r) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r) {
        tree[x].tag ^= 1;
        tree[x].v *= -1;
        swap(tree[x].max, tree[x].min);
        tree[x].max *= -1, tree[x].min *= -1;
        return;
    }
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        reverse_tree(x<<1, l, r);
    if(r > mid)
        reverse_tree(x<<1|1, l, r);
    pushup(x);
    return;
}

inline int query_sum(int x, int l, int r) {
    //printf("querysum %d->[%d,%d]\n", x, l, r);
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r)
        return tree[x].v;
    pushdown(x);
    int mid = (ll + rr) >> 1;
    int res = 0;
    if(l <= mid)
        res += query_sum(x<<1, l, r);
    if(r > mid)
        res += query_sum(x<<1|1, l, r);
    return res;
}

inline int query_max(int x, int l, int r) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r)
        return tree[x].max;
    pushdown(x);
    int res = -INF;
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        res = max(res, query_max(x<<1, l, r));
    if(r > mid)
        res = max(res, query_max(x<<1|1, l, r));
    return res;
}

inline int query_min(int x, int l, int r) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r)
        return tree[x].min;
    pushdown(x);
    int res = INF;
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        res = min(res, query_min(x<<1, l, r));
    if(r > mid)
        res = min(res, query_min(x<<1|1, l, r));
    return res;
}

inline int Sum(int u, int v) {
    int res = 0;
    while(top[u] != top[v]) {
        if(depth[top[u]] < depth[top[v]])
            swap(u, v);
        res += query_sum(1, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if(dfn[u] > dfn[v])
        swap(u, v);
    res += query_sum(1, dfn[u]+1, dfn[v]);
    return res;
}

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

inline int Max(int u, int v) {
    int res = -INF;
    while(top[u] != top[v]) {
        if(depth[top[u]] < depth[top[v]])
            swap(u, v);
        res = max(res, query_max(1, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if(dfn[u] > dfn[v])
        swap(u, v);
    res = max(res, query_max(1, dfn[u]+1, dfn[v]));
    return res;
}

inline int Min(int u, int v) {
    int res = INF;
    while(top[u] != top[v]) {
        if(depth[top[u]] < depth[top[v]])
            swap(u, v);
        res = min(res, query_min(1, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if(dfn[u] > dfn[v])
        swap(u, v);
    res = min(res, query_min(1, dfn[u]+1, dfn[v]));
    return res;
}

int main() {
    n = read();
    for(register int i = 1; i < n; i++) {
        int u, v, w;
        u = read() + 1, v = read() + 1, w = read();
        build_edge(u, v, w);
        build_edge(v, u, w);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    build_tree(1, 1, n);
    int m = read();
    while(m--) {
        char s[10];
        int a, b;
        scanf("%s", s);
        a = read(); b = read();
        if(s[0] == 'C')
            edit_tree(1, dfn[++a], b);
        else if(s[0] == 'N')
            Reverse(++a, ++b);
        else if(s[0] == 'S')
            printf("%d\n", Sum(++a, ++b));
        else if(s[1] == 'A')
            printf("%d\n", Max(++a, ++b));
        else
            printf("%d\n", Min(++a, ++b));
    }
    return 0;
}

例题 P4315

这道题的核心就是如何正确地打 线段树 ,以及如何处理单独修改边权的问题。

修改第$\textbf{u}$条边时,加上这句话:

u = depth[edge[(u<<1)-1].to] < depth[edge[u<<1].to] ? edge[u<<1].to : edge[(u<<1)-1].to;

意思是说,判断当前这条边的边权投影到的是哪个点。由于输入的$u$是表示第$u$条边,由于我们存的是无向边,所以$2u-1$、$2u$编号的边都是“第$u$条边”,由于投影时是将边权保存到边的后向点,所以只需要找到深度最大的那个点即可。


完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int INF = 1 << 30;
struct EDGE {
    int to, next;
    int val;
} edge[MAXN];
int last[MAXN], id = 0;
struct SEGTREE {
    int l, r;
    int tag, c, max;
} tree[MAXN << 2];

inline void build_edge(int u, int v, int val) {
    edge[++id].to = v;
    edge[id].val = val;
    edge[id].next = last[u];
    last[u] = id;
    return;
}

int n, w[MAXN];
int fa[MAXN], depth[MAXN], size[MAXN], son[MAXN];
int top[MAXN], dfn[MAXN], rev[MAXN], cnt = 0;

inline void dfs1(int u, int father) {
    fa[u] = father, depth[u] = depth[father] + 1;
    size[u] = 1;
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == father)
            continue;
        w[v] = edge[i].val;
        dfs1(v, u);
        size[u] += size[v];
        if(size[v] > size[son[u]])
            son[u] = v;
    }
    return;
}

inline void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++cnt, rev[cnt] = u;
    if(!son[u])
        return;
    dfs2(son[u], t);
    for(register int i = last[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
    return;
}

inline void pushdown(int x) {
    if(~tree[x].c) {
        tree[x<<1].max = tree[x<<1|1].max = tree[x].c;
        tree[x<<1].c = tree[x<<1|1].c = tree[x].c;
        tree[x<<1].tag = tree[x<<1|1].tag = 0;
        tree[x].c = -1;
    }
    if(tree[x].tag) {
        tree[x<<1].max += tree[x].tag;
        tree[x<<1|1].max += tree[x].tag;
        tree[x<<1].tag += tree[x].tag;
        tree[x<<1|1].tag += tree[x].tag;
        tree[x].tag = 0;
    }
    return;
}

inline void pushup(int x) {
    tree[x].max = max(tree[x<<1].max, tree[x<<1|1].max);
    return;
}

inline void build_tree(int x, int l, int r) {
    tree[x].l = l, tree[x].r = r;
    tree[x].tag = 0, tree[x].c = -1;
    if(l == r) {
        tree[x].max = w[rev[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(x<<1, l, mid);
    build_tree(x<<1|1, mid + 1, r);
    pushup(x);
    return;
}

inline void cover(int x, int l, int r, int c) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r) {
        tree[x].max = tree[x].c = c;
        tree[x].tag = 0;
        return;
    }
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        cover(x<<1, l, r, c);
    if(r > mid)
        cover(x<<1|1, l, r, c);
    pushup(x);
    return;
}

inline void add(int x, int l, int r, int c) {
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r) {
        tree[x].max += c;
        tree[x].tag += c;
        return;
    }
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        add(x<<1, l, r, c);
    if(r > mid)
        add(x<<1|1, l, r, c);
    pushup(x);
    return;
}

inline int query(int x, int l, int r) {
    int res = -INF;
    int ll = tree[x].l, rr = tree[x].r;
    if(l <= ll && rr <= r)
        return tree[x].max;
    pushdown(x);
    int mid = (ll + rr) >> 1;
    if(l <= mid)
        res = max(res, query(x<<1, l, r));
    if(r > mid)
        res = max(res, query(x<<1|1, l, r));
    return res;
}

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

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

inline int Max(int u, int v) {
    int res = -INF;
    while(top[u] != top[v]) {
        if(depth[top[u]] < depth[top[v]])
            swap(u, v);
        res = max(res, query(1, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if(dfn[u] > dfn[v])
        swap(u, v);
    res = max(res, query(1, dfn[u] + 1, dfn[v]));
    return res;
}

int main() {
    scanf("%d", &n);
    for(register int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        build_edge(u, v, w);
        build_edge(v, u, w);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    build_tree(1, 1, n);
    char s[10];
    scanf("%s", s);
    while(s[0] != 'S') {
        switch(s[1]) {
            case 'a': {
                int u, v;
                scanf("%d%d", &u, &v);
                printf("%d\n", Max(u, v));
                break;
            }
            case 'o': {
                int u, v, c;
                scanf("%d%d%d", &u, &v, &c);
                Cover(u, v, c);
                break;
            }
            case 'd': {
                int u, v, c;
                scanf("%d%d%d", &u, &v, &c);
                Add(u, v, c);
                break;
            }
            case 'h': {
                int u, c;
                scanf("%d%d", &u, &c);
                u = depth[edge[(u<<1)-1].to] < depth[edge[u<<1].to] ? edge[u<<1].to : edge[(u<<1)-1].to;
                cover(1, dfn[u], dfn[u], c);
                break;
            }
        }
        scanf("%s", s);
    }
    return 0;
}