FZU 2082 过路费
树链抛分改动边的模板题
代码：
#include#include #include using namespace std;typedef long long ll;const int N = 50005;int dep[N], id[N], sz[N], top[N], son[N], fa[N], idx;int n, m;ll bit[N];struct Edge { int u, v; ll val; void read() { scanf("%d%d%lld", &u, &v, &val); }} e[N];vector g[N];inline int lowbit(int x) { return x&(-x);}void dfs1(int u, int f, int d) { dep[u] = d; sz[u] = 1; fa[u] = f; son[u] = 0; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v == f) continue; dfs1(v, u, d + 1); sz[u] += sz[v]; if (sz[son[u]] < sz[v]) son[u] = v; }}void dfs2(int u, int tp) { top[u] = tp; id[u] = idx++; if (son[u]) dfs2(son[u], tp); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v == fa[u] || v == son[u]) continue; dfs2(v, v); }}void add(int x, ll v) { while (x < N) { bit[x] += v; x += lowbit(x); }}ll query(int x) { ll ans = 0; while (x) { ans += bit[x]; x -= lowbit(x); } return ans;}ll query(int l, int r) { return query(r) - query(l - 1);}ll gao(int u, int v) { int tp1 = top[u], tp2 = top[v]; ll ans = 0; while (tp1 != tp2) { if (dep[tp1] < dep[tp2]) { swap(tp1, tp2); swap(u, v); } ans += query(id[tp1], id[u]); u = fa[tp1]; tp1 = top[u]; } if (u == v) return ans; if (dep[u] > dep[v]) swap(u, v); ans += query(id[son[u]], id[v]); return ans;}int main() { while (~scanf("%d%d", &n, &m)) { idx = 0; memset(bit, 0, sizeof(bit)); for (int i = 1; i <= n; i++) g[i].clear(); for (int i = 1; i < n; i++) { e[i].read(); g[e[i].u].push_back(e[i].v); g[e[i].v].push_back(e[i].u); } dfs1(1, 0, 1); dfs2(1, 1); for (int i = 1; i < n; i++) { if (dep[e[i].u] < dep[e[i].v]) swap(e[i].u, e[i].v); add(id[e[i].u], e[i].val); } int ty, a, b; while (m--) { scanf("%d%d%d", &ty, &a, &b); if (ty == 0) { ll tmp = query(id[e[a].u], id[e[a].u]); add(id[e[a].u], (ll)b - tmp); } else printf("%lld\n", gao(a, b)); } } return 0;}