P3178求助

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int M = 2 * N;
struct SegmentTree {
	int l, r, add, sum;
} tree[8 * N];
int n, m, a[N], in[N], out[N], vis[M];
int head[N], ver[M], nxt[M], c[M], num[M];
int dfn, tot;
void add_edge(int x, int y) {
	ver[++tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
}
void dfs(int x, int fa) {
	in[x] = ++dfn;
	num[dfn] = x;
	vis[dfn] = 1;
	for (int i = head[x]; i; i = nxt[i]) {
		int to = ver[i];
		if (to != fa)
			dfs(to, x);
	}
	out[x] = ++dfn;
	num[dfn] = x;
	vis[dfn] = -1;
}
void build(int p, int l, int r) {
	tree[p].l = l, tree[p].r = r;
	if (l == r) {
		tree[p].sum = vis[l] * a[num[l]];
		return;
	}
	int mid = (l + r) / 2;
	build(p * 2, l, mid);
	build(p * 2 + 1, mid + 1, r);
	tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
void spread(int p) {
	int add = tree[p].add;
	tree[p * 2].sum += add * (c[tree[p * 2].r] - c[tree[p * 2].l - 1]);
	tree[p * 2 + 1].sum += add * (c[tree[p * 2 + 1].r] - c[tree[p * 2 + 1].l - 1]);
	tree[p * 2].add += add;
	tree[p * 2 + 1].add += add;
	tree[p].add = 0;
}
void change(int p, int id, int d) {
	int l = tree[p].l, r = tree[p].r;
	if (l == id && r == id) {
		tree[p].sum += d;
		return;
	}
	spread(p);
	int mid = (l + r) / 2;
	if (mid >= id) change(p * 2, id, d);
	else change(p * 2 + 1, id, d);
	tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
	return;
}
void update(int p, int l, int r, int d) {
	int L = tree[p].l, R = tree[p].r;
	if (l <= L && r >= R) {
		tree[p].sum += d * (c[R] - c[L - 1]);
		tree[p].add += d;
		return;
	}
	if (tree[p].add) spread(p);
	int mid = (L + R) / 2;
	if (l <= mid) update(p * 2, l, r, d);
	if (r > mid) update(p * 2 + 1, l, r, d);
	tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}
int query(int p, int l, int r) {
	int val = 0;
	if (l <= tree[p].l && r >= tree[p].r)
		return tree[p].sum;
	if (tree[p].add) spread(p);
	int mid = (tree[p].l + tree[p].r) / 2;
	if (l <= mid) val += query(p * 2, l, r);
	if (r > mid) val + query(p * 2 + 1, l, r);
	return val;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		add_edge(x, y);
		add_edge(y, x);
	}
	dfs(1, 0);
	for (int i = 1; i <= dfn; i++)
		c[i] = c[i - 1] + vis[i];
	build(1, 1, n * 2);
	for (int i = 1; i <= m; i++) {
		int op, x, d;
		cin >> op;
		if (op == 1) {
			cin >> x >> d;
			change(1, in[x], d);
			change(1, out[x], -d);
		}
		if (op == 2) {
			cin >> x >> d;
			update(1, in[x], out[x], d);
		}
		if (op == 3) {
			cin >> x;
			cout << query(1, 1, in[x]) << endl;
		}
	}
	return 0;
}