也是入门题，和上一题不一样的是权值在边上。
调了半天后来发现线段树写错了，build的时候没有pushup。。。蠢哭了好吗。。。。
做题还是不专心，太慢辣。。
#include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int N = 100005; /** 树链剖分 权值在边上 所以把权值赋给每个边连着的向下的结点 因为每个点有且只有一个父节点（除了根 因为更新的是边，所以对于每一个边记录它对应的点 更新的时候会多更新一个边 因为父节点上边的也会更新到 实际上并不需要 处理方法就是 更新最后一条链的时候 更新从父节点的子节点开始 */ // struct Edge { int to, next, cost, id; } edge[N*2]; int head[N], cntE; void addedge(int u, int v, int w, int id) { edge[cntE].to = v; edge[cntE].next = head[u]; edge[cntE].cost = w; edge[cntE].id = id; head[u] = cntE++; edge[cntE].to = u; edge[cntE].next = head[v]; edge[cntE].cost = w; edge[cntE].id = id; head[v] = cntE++; } // int dep[N], sz[N], fa[N], son[N], son_cost[N]; int road[N]; void dfs1(int u, int par, int d) { dep[u] = d; sz[u] = 1; fa[u] = par; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (v != par) { road[edge[i].id] = v; dfs1(v, u, d+1); sz[u] += sz[v]; if (son[u] == -1 || sz[v] > sz[son[u]]) { son[u] = v; son_cost[u] = edge[i].cost; } } } } int top[N], dfn[N], rk[N], idx; int a[N]; void dfs2(int u, int rt, int cost) { top[u] = rt; dfn[u] = ++idx; a[idx] = cost; if (son[u] == -1) return; dfs2(son[u], rt, son_cost[u]); for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (v != fa[u] && v != son[u]) dfs2(v, v, edge[i].cost); } } // int tr[N<<2]; void build(int o, int l, int r) { if (l == r) { tr[o] = a[l]; } else { int mid = (l+r) >> 1; build(o<<1, l, mid); build(o<<1|1, mid+1, r); tr[o] = tr[o<<1] + tr[o<<1|1]; } } void update(int o, int l, int r, int v, int w) { if (l == r) { tr[o] = w; } else { int mid = (l + r) >> 1; if (mid >= v) update(o<<1, l, mid, v, w); else update(o<<1|1, mid+1, r, v, w); tr[o] = tr[o<<1] + tr[o<<1|1]; } } int query(int o, int l, int r, int L, int R) { if (l >= L && r <= R) return tr[o]; if (l > R && r < L) return 0; int mid = (l+r) >> 1; int ans = 0; if (L <= mid) ans += query(o<<1, l, mid, L, R); if (R > mid) ans += query(o<<1|1, mid+1, r, L, R); return ans; } int change(int x, int y, int n) { int ans = 0; while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); ans += query(1, 1, n, dfn[top[x]], dfn[x]); x = fa[top[x]]; } if (x == y) return ans; if (dep[x] > dep[y]) swap(x, y); ans += query(1, 1, n, dfn[son[x]], dfn[y]); // 注意这里是son[x] return ans; } void init() { idx = cntE = 0; memset(head, -1, sizeof head); memset(son, -1, sizeof son); } // 单点更新 区间查询 int main() { int n, q, s; while (~scanf("%d%d%d", &n, &q, &s)) { init(); int u, v, w; int op; for (int i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), addedge(u, v, w, i); dfs1(1, 0, 0); dfs2(1, 1, 0); build(1, 1, n); while (q--) { scanf("%d", &op); if (op == 0) { scanf("%d", &u); v = s; s = u; printf("%d ", change(u, v, n)); } else { scanf("%d%d", &u, &w); update(1, 1, n, dfn[road[u]], w); } } } return 0; } /** 3 3 1 1 2 1 1 3 2 0 2 1 1 2 0 3 1 4 */