Description
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种： 操作 1 ：把某个节点 x 的点权增加 a 。 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。 接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。 再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操 作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
Output
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
Sample Input
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
Sample Output
6
9
13
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不 会超过 10^6。
Source
一道树链剖分的题目。剖完之后放到线段树里维护就可以啦！ 对于操作一，既是线段数单点修改；对于操作二，在dfs_2中记录一下dfs序即可，因为一棵子树中所有的节点在序列中的位置是连续的。直接区间修改。对于操作三，普通的查询…… 不过要吐槽一下……因为int 和 long long 之间的蜜汁错误，我和某神犇调了好久……@a【哭晕】 一定要注意……int 和 long long 相乘会返回int值……mdzz
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; typedef long long LL; const int SZ = 300010; const int root = 1; struct Edge { int f, t; }es[SZ]; struct SGT { int l, r; LL sum, add; }tree[SZ << 2]; int num[SZ], first[SZ << 1], nxt[SZ << 1], tot = 1; void insert(int f, int t) { es[++tot] = (Edge){f, t}; nxt[tot] = first[f]; first[f] = tot; } int fa[SZ], depth[SZ], size[SZ], son[SZ]; void dfs_1(int u, int f) { fa[u] = f; depth[u] = depth[f] + 1; size[u] = 1; for(int i = first[u]; i; i = nxt[i]) { int v = es[i].t; if(v == f) continue; dfs_1(v, u); size[u] += size[v]; if(!son[u] || size[v] > size[son[u]]) son[u] = v; } } int top[SZ], topa, inseg[SZ], intree[SZ], in[SZ], out[SZ]; void dfs_2(int u, int topu) { top[u] = topu; inseg[u] = ++topa; in[u] = topa; out[u] = topa; intree[topa] = u; if(!son[u]) return ; dfs_2(son[u], topu); for(int i = first[u]; i; i = nxt[i]) { int v = es[i].t; if(v == fa[u] || v == son[u]) continue; dfs_2(v, v); } out[u] = topa; } void update(int now) { tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum; } void build(int now, int l, int r) { tree[now].l = l; tree[now].r = r; if(l == r) { tree[now].sum = num[intree[l]]; return ; } int mid = (l + r) >> 1; build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r); update(now); } void pushdown(int now) { if(tree[now].add) { tree[now << 1].sum += (tree[now << 1].r - tree[now << 1].l + 1) * tree[now].add; tree[now << 1].add += tree[now].add; tree[now << 1 | 1].sum += (tree[now << 1 | 1].r - tree[now << 1 | 1].l + 1) * tree[now].add; tree[now << 1 | 1].add += tree[now].add; tree[now].add = 0; update(now); } } void change(int now, int l, int r, LL value) { if(l <= tree[now].l && tree[now].r <= r) { tree[now].sum += (tree[now].r - tree[now].l + 1) * value; tree[now].add += value; return; } pushdown(now); int mid = (tree[now].l + tree[now].r) >> 1; if(l <= mid) change(now << 1, l, r, value); if(r > mid) change(now << 1 | 1, l, r, value); update(now); } LL ask_sum(int now, int l, int r) { if(l <= tree[now].l && tree[now].r <= r) return tree[now].sum; pushdown(now); LL ans = 0; int mid = (tree[now].l + tree[now].r) >> 1; if(l <= mid) ans += ask_sum(now << 1, l, r); if(r > mid) ans += ask_sum(now << 1 | 1, l, r); return ans; } LL Sum(int x) { int fal = top[x], far = top[root]; LL ans = 0; while(fal != far) { LL ha = ask_sum(1, inseg[fal], inseg[x]); ans += ha; x = fa[fal]; fal = top[x]; } ans += ask_sum(1, inseg[root], inseg[x]); return ans; } int read() { char c = getchar(); bool flag = 0; int s = 0; while(c < '0' || c > '9') { if(c == '-') flag = 1; c = getchar(); } while('0' <= c && c <= '9') { s = s * 10 + (c - '0'); c = getchar(); } return flag == 1 ? (-s) : s; } int main() { int n, m; n = read(); m = read(); for(int i = 1; i <= n; i++) num[i] = read(); int f, t; for(int i = 1;i < n; i++) { f = read(); t = read(); insert(f, t); insert(t, f); } dfs_1(1, 0); dfs_2(1, 1); build(1, 1, n); int op, x, a; for(int i = 1; i <= m; i++) { op = read(); x = read(); if(op == 1) { a = read(); change(1, inseg[x], inseg[x], (LL)a); } if(op == 2) { a = read(); change(1, in[x], out[x], (LL)a); } if(op == 3) printf("%lld\n", Sum(x)); } return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017043.html
