将一棵树剖分成log条树链，用数据结构维护每一段树链，操作复杂度从n降为log(n)*log(n).
#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> #include<set> #include<stack> #define LL int using namespace std; const int N = 50000+15; LL n, m, p; LL ene[N]; vector<int> g[N]; LL tim = 1; LL siz[N];//子树大小 LL top[N];//当前top节点 LL son[N];//重儿子 LL dep[N];//深度 LL fa[N];//父亲 LL tid[N];//节点->新编号 LL rnk[N];//编号->节点 void dfs1(LL now, LL p,LL deep) { siz[now] = 1; dep[now] = deep; fa[now] = p; son[now] = -1; for (int i = 0; i < g[now].size(); i++) { int e = g[now][i]; if (e == p) continue; dfs1(e, now, deep + 1); siz[now] += siz[e]; if (son[now] == -1 || siz[son[now]] < siz[e]) son[now] = e; } } void dfs2(int now,int tp) { //这两者需要根据dfs2顺序而设置 tid[now] = tim++; rnk[tid[now]] = now; top[now] = tp; if (son[now] == -1)return; dfs2(son[now], tp); for (int i = 0; i < g[now].size(); i++) { LL e = g[now][i]; if (e == fa[now]||e==son[now]) continue; dfs2(e, e); } } struct SegTree { struct node { LL l, r; LL v; }; node tre[N << 2]; void build(LL l, LL r, LL rt) { tre[rt].l = l; tre[rt].r = r; tre[rt].v = 0; if (l == r) { tre[rt].v = ene[rnk[l]]; return; } LL mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); } void pushDown(LL rt) { tre[rt << 1].v += tre[rt].v; tre[rt << 1 | 1].v += tre[rt].v; tre[rt].v = 0; } int query(LL p, LL rt) { if (tre[rt].l == tre[rt].r)return tre[rt].v; //if (tre[rt].v)pushDown(rt); int mid = (tre[rt].l + tre[rt].r) >> 1; if (p <= mid) return tre[rt].v+query(p, rt << 1); return tre[rt].v+query(p, rt << 1 | 1); } void update(LL rt, LL l, LL r, LL v) { if (l <= tre[rt].l&&tre[rt].r <= r) { tre[rt].v += v; return; } //if (tre[rt].v)pushDown(rt); LL mid = (tre[rt].l + tre[rt].r) >> 1; if (l <= mid) update(rt << 1, l, r, v); if (r > mid) update(rt << 1 | 1, l, r, v); } }t; void change(LL u, LL v, LL k) { while (top[u] != top[v])//深点向浅点靠近，直到在同一条链上 { if (dep[top[v]] < dep[top[u]]) swap(u, v); t.update(1, tid[top[v]], tid[v], k); v = fa[top[v]]; } if (dep[u] > dep[v])swap(u, v); t.update(1, tid[u], tid[v], k); } int main() { cin.sync_with_stdio(false); while (scanf("%d%d%d",&n,&m,&p)!=EOF) { for (int i = 0; i <= n; i++) g[i].clear(); for (int i = 1; i <= n; i++)scanf("%d", &ene[i]); for (int i = 0; i < m; i++) { int uu, vv; scanf("%d%d", &uu, &vv); g[uu].push_back(vv); g[vv].push_back(uu); } tim = 1; dfs1(1,0,0);//第一遍构造重边 dfs2(1,1);//第二遍构造重链 t.build(1, n, 1); while (p--) { char c[2]; LL c1, c2, value; scanf("%s",c); if (c[0] == 'I') { scanf("%d%d%d", &c1, &c2, &value); change(c1, c2, value); } if (c[0] == 'D') { scanf("%d%d%d", &c1, &c2, &value); change(c1, c2, -value); } if (c[0] == 'Q') { scanf("%d", &c1); cout << t.query(tid[c1],1) << endl; } } } return 0; }