题意：给定一棵含n个结点的生成树，共有q次操作，分为两种： 0 c：求从位置s到c的距离，然后s变成c 1 a b：把第a条边的权值变为b
题解：树链剖分 0操作就是树上区间查询。
由于该题是边权且为生成树，树链剖分只能解决点权，那我们化成点权即可。即对于边<u, v>，将离根节点远的那个点的权值赋为边权。
这样在进行树剖的时候，减去lca的点权即可。
这样1操作就是单点更新了。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<fstream> #include<set> #include<map> #include<sstream> #include<iomanip> #define ll long long #define pii pair<int, int> using namespace std; const int MAXN = 1e5 + 5; int n, q, s, x[MAXN], y[MAXN], w[MAXN]; int sum[MAXN << 2], add[MAXN << 2]; int head[MAXN << 1], pre[MAXN], id[MAXN]; int siz[MAXN], son[MAXN], fa[MAXN]; int dep[MAXN], top[MAXN]; ll delta[MAXN]; struct edge { int to; int next; }e[MAXN << 1]; int tot, sign; /*------------准备阶段--------------*/ void init() { memset(head, -1, sizeof(head)); memset(id, 0, sizeof(id)); memset(siz, 0, sizeof(siz)); memset(son, 0, sizeof(son)); memset(fa, 0, sizeof(fa)); memset(dep, 0, sizeof(dep)); memset(top, 0, sizeof(top)); memset(delta, 0, sizeof(delta)); tot = sign = 0; } void addedge(int u, int v) { e[tot].to = v, e[tot].next = head[u], head[u] = tot++; } /*--------------dfs-----------------*/ void dfs1(int u, int f) { //1 0 dep[u] = dep[f] + 1; fa[u] = f; siz[u] = 1; for (int i = head[u]; i != -1; i = e[i].next) { int to = e[i].to; if (to == f) continue; dfs1(to, u); siz[u] += siz[to]; if (siz[to] > siz[son[u]]) son[u] = to; } } void dfs2(int u, int Top) { //1 1 id[u] = ++sign; pre[sign] = u; top[u] = Top; if (son[u]) dfs2(son[u], Top); for (int i = head[u]; i != -1; i = e[i].next) { int to = e[i].to; if (to == son[u] || to == fa[u]) continue; dfs2(to, to); } } /*--------------树状数组--------------*/ int tree[MAXN]; void update(int x, int num) { for (; x <= n; x += x & -x) tree[x] += num;; } int su(int x) { int answer = 0; for (; x > 0; x -= x & -x) answer += tree[x]; return answer; } /*------------树链剖分-------------*/ int getSum(int x, int y) { //查询x到y路径上所有结点和 ll res = 0; while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); res += su(id[x]) - su(id[top[x]] - 1); x = fa[top[x]]; } if (id[x] > id[y]) swap(x, y); res += su(id[y]) - su(id[x]); //减去lca return res; } int main() { init(); scanf("%d%d%d", &n, &q, &s); for (int i = 1; i < n; i++) { scanf("%d%d%d", &x[i], &y[i], &w[i]); addedge(x[i], y[i]); addedge(y[i], x[i]); } dfs1(1, 0); dfs2(1, 1); for (int i = 1; i < n; i++) { if (fa[x[i]] == y[i]) swap(x[i], y[i]); update(id[y[i]], w[i]); } int op, a, b; while (q--) { scanf("%d", &op); if (op == 0) { scanf("%d", &a); printf("%d\n", getSum(s, a)); s = a; } else { scanf("%d%d", &a, &b); update(id[y[a]], b - w[a]); w[a] = b; } } return 0; }