解题思路

本题只有两种操作：求树上两点间路径的权值和、修改边权。

于是使用树链剖分就很简单了。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

const int MAXN = 100001;

struct edge_orig {
    int u, v;
    int w;
} edge[MAXN];

struct edge {
    int to;
    int next;
} e[MAXN<<1];

int n, q, s, a, b, op;
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN];
int idx, id[MAXN], top[MAXN], val[MAXN];
int head[MAXN], cnt;
int SUM[MAXN<<2];

void Add(int u, int v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void DFS1(int u, int pre, int d) {
    dep[u] = d;
    sz[u] = 1;
    son[u] = 0;
    fa[u] = pre;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v = e[i].to;
        if(v != pre) {
            DFS1(v, u, d+1);
            sz[u] += sz[v];
            if(sz[v] > sz[son[u]])
                son[u] = v;
        }
    }
}

void DFS2(int u, int t) {
    top[u] = t;
    id[u] = ++idx;
    if(son[u]) DFS2(son[u], t);
    for(int i=head[u]; ~i; i=e[i].next) {
        int v = e[i].to;
        if(v!=fa[u] && v!=son[u])
            DFS2(v, v);
    }
}

void PushUp(int rt) {
    SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
}

void Build(int l, int r, int rt) {
    if(l == r) {
        SUM[rt] = val[l];
        return;
    }
    int m = (l + r) >> 1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

void Update(int p, int v, int l, int r, int rt) {
    if(l == r) {
        SUM[rt] = v;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m) Update(p, v,lson);
    else Update(p, v, rson);
    PushUp(rt);
}

int Query(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return SUM[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) ret += Query(L, R, lson);
    if(R > m) ret += Query(L, R, rson);

    return ret;
}

int GetAns(int u, int v) {
    int ans = 0;
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        ans += Query(id[top[u]], id[u], 1, n, 1);
        u = fa[top[u]];
    }
    if(u == v) return ans;
    if(dep[u] > dep[v]) swap(u, v);
    ans += Query(id[son[u]], id[v], 1, n, 1);

    return ans;
}

int main(int argc, char const *argv[]) {
    memset(head, -1, sizeof head);
    scanf("%d %d %d", &n, &q, &s);
    for(int i=1; i<=n-1; ++i) {
        scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
        Add(edge[i].u, edge[i].v);
        Add(edge[i].v, edge[i].u);
    }
    idx = 0;
    DFS1(1, -1, 1);
    DFS2(1, 1);
    for(int i=1; i<=n-1; ++i) {
        if(dep[edge[i].u] < dep[edge[i].v])
            swap(edge[i].u, edge[i].v);
        val[id[edge[i].u]] = edge[i].w;
    }
    Build(1, n, 1);
    while(q--) {
        scanf("%d", &op);
        if(op == 0) {
            scanf("%d", &a);
            printf("%d\n", GetAns(s, a));
            s = a;
        }
        else {
            scanf("%d %d", &a, &b);
            Update(id[edge[a].u], b, 1, n, 1);
        }
    }
    
    return 0;
}