思路：
用dfs序+线段树维护子树中距离（从1到u，再从u到1）的最小值
代码：
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 2e5 + 5; const LL INF = 0x3f3f3f3f3f3f3f3f; int L[N], R[N], anc[N][20], deep[N], f[N], b[N], bb[N], head[N], cnt = 1, now = 1; LL tree[N<<2], lazy[N<<2], a[N]; struct edge { int from, to, w, nxt; }edge[N]; void add_edge(int u, int v, int w) { edge[cnt].from = u; edge[cnt].to = v; edge[cnt].w = w; edge[cnt].nxt = head[u]; head[u] = cnt++; } void push_up(int rt) { tree[rt] = min(tree[rt<<1], tree[rt<<1|1]); } void push_down(int rt) { lazy[rt<<1] += lazy[rt]; lazy[rt<<1|1] += lazy[rt]; tree[rt<<1] += lazy[rt]; tree[rt<<1|1] += lazy[rt]; lazy[rt] = 0; } void build(int rt, int l, int r) { if(l == r) { tree[rt] = a[f[l]]; return ; } int m = l+r >> 1; build(ls); build(rs); push_up(rt); } void update(int L, int R, int v, int rt, int l, int r) { if(L <= l && r <= R) { tree[rt] += v; lazy[rt] += v; return ; } if(lazy[rt]) push_down(rt); int m = l+r >> 1; if(L <= m) update(L, R, v, ls); if(R > m) update(L, R, v, rs); push_up(rt); } LL query(int L, int R, int rt, int l, int r) { if(L <= l && r <= R) return tree[rt]; if(lazy[rt]) push_down(rt); int m = l+r >> 1; LL ans = INF; if(L <= m) ans = min(ans, query(L, R, ls)); if(R > m) ans = min(ans, query(L, R, rs)); push_up(rt); return ans; } void dfs(int u) { L[u] = now; f[now] = u; for (int i = head[u]; ~i; i = edge[i].nxt) { int v = edge[i].to; anc[v][0] = u; for (int j = 1; j < 20; j++) anc[v][j] = anc[anc[v][j-1]][j-1]; deep[v] = deep[u] + 1; now++; a[v] = a[u] - b[u] + edge[i].w + b[v]; dfs(v); } R[u] = now; } int lca(int u, int v) { if(deep[u] < deep[v]) swap(u, v); for (int i = 19; i >= 0; i--) if(deep[anc[u][i]] >= deep[v]) u = anc[u][i]; if(u == v) return u; for (int i = 19; i >= 0; i--) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i]; return anc[u][0]; } int main() { int n, q, ty, u, v, w; mem(head, -1); scanf("%d %d", &n, &q); for (int i = 1; i < n; i++) { scanf("%d %d %d", &u, &v, &w); add_edge(u, v, w); } for (int i = 1; i < n; i++) { scanf("%d %d %d", &u, &v, &w); b[u] = w; bb[i] = u; } for (int i = 0; i < 20; i++) anc[1][i] = 1; dfs(1); build(1, L[1], R[1]); while(q--) { scanf("%d %d %d", &ty, &u, &v); if(ty == 1) { if(u >= n) { int nod = bb[u-n+1]; int add = v - b[nod]; update(L[nod], L[nod], add, 1, L[1], R[1]); b[nod] = v; } else { int nod = edge[u].to; int add = v - edge[u].w; update(L[nod], R[nod], add, 1, L[1], R[1]); edge[u].w = v; } } else { int l = lca(u, v); LL ans = INF; if(l == u) { LL dis1 = query(L[u], L[u], 1, L[1], R[1]) - b[u]; LL dis2 = query(L[v], L[v], 1, L[1], R[1]) - b[v]; ans = dis2 - dis1; } else { LL dis1 = query(L[u], R[u], 1, L[1], R[1]) - (query(L[u], L[u], 1, L[1], R[1]) - b[u]); LL dis2 = query(L[v], L[v], 1, L[1], R[1]) - b[v]; ans = dis1 + dis2; } printf("%lld ", ans); } } return 0; }