【数据结构树树链剖分】luogu_3178 [HAOI2015]树上操作

本文主要是介绍【数据结构树树链剖分】luogu_3178 [HAOI2015]树上操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：

操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

思路

一道树链剖分裸题，这次是默写板子。

代码

#include <cstdio>struct segmentTree {int l, r, ls, rs;long long dat, lazy;
}t[200001];
int n, m, tot, cnt;
int a[100001];
int head[100001], ver[200001], next[200001];
int father[100001], dep[100001], size[100001], seg[100001], rev[100001], son[100001], top[100001];void dfs1(int p, int fa) {father[p] = fa;dep[p] = dep[fa] + 1;size[p] = 1;for (int i = head[p]; i; i = next[i]) {if (ver[i] == fa) continue;dfs1(ver[i], p);size[p] += size[ver[i]];if (size[son[p]] < size[ver[i]]) son[p] = ver[i];}
}void dfs2(int p, int t) {seg[p] = ++cnt;rev[cnt] = p;top[p] = t;if (!son[p]) return;dfs2(son[p], t);for (int i = head[p]; i; i = next[i]) {if (ver[i] == father[p] || ver[i] == son[p]) continue;dfs2(ver[i], ver[i]);}
}void add(int u, int v) {ver[++tot] = v;next[tot] = head[u];head[u] = tot;
}void build(int p, int l, int r) {t[p].l = l, t[p].r = r;if (l == r) {t[p].dat = a[rev[l]];return;}int mid = l + r >> 1;build(t[p].ls = ++cnt, l, mid);build(t[p].rs = ++cnt, mid + 1, r);t[p].dat = t[t[p].ls].dat + t[t[p].rs].dat;
}void spread(int p) {if (!t[p].lazy) return;t[t[p].ls].lazy += t[p].lazy;t[t[p].rs].lazy += t[p].lazy;t[t[p].ls].dat += (long long)(t[t[p].ls].r - t[t[p].ls].l + 1) * t[p].lazy;t[t[p].rs].dat += (long long)(t[t[p].rs].r - t[t[p].rs].l + 1) * t[p].lazy;t[p].lazy = 0;
}void update(int p, int l, int r, int val) {if (l <= t[p].l && t[p].r <= r) {t[p].lazy += val;t[p].dat += (long long)(t[p].r - t[p].l + 1) * val;return;}spread(p);int mid = t[p].l + t[p].r >> 1;if (l <= mid) update(t[p].ls, l, r, val);if (r > mid) update(t[p].rs, l, r, val);t[p].dat = t[t[p].ls].dat + t[t[p].rs].dat;
}long long query(int p, int l, int r) {if (l <= t[p].l && t[p].r <= r)return t[p].dat;spread(p);int mid = t[p].l + t[p].r >> 1;long long res = 0;if (l <= mid) res += query(t[p].ls, l, r);if (r > mid) res += query(t[p].rs, l, r);return res;
}long long ask(int x) {long long res = 0;while (top[x] != 1) {res += query(1, seg[top[x]], seg[x]);x = father[top[x]];}res += query(1, 1, seg[x]);return res;
}int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);for (int i = 1, x, y; i < n; i++) {scanf("%d %d", &x, &y);add(x, y), add(y, x);}dfs1(1, 0);dfs2(1, 1);build(cnt = 1, 1, n);for (int op, x, y; m; m--) {scanf("%d", &op);if (op == 1) {scanf("%d %d", &x, &y);update(1, seg[x], seg[x], y);} else if (op == 2) {scanf("%d %d", &x, &y);update(1, seg[x], seg[x] + size[x] - 1, y);} else {scanf("%d", &x);printf("%lld\n", ask(x));}}
}