树链剖分加线段树

#include<bits/stdc++.h>

#define mid ((l + r) >> 1ll)

using namespace std;

const long long N = 100010ll;

vector <long long> e[N];

long long top[N], dep[N], son[N], size[N], f[N];

long long sum[N << 3], dfn[N], wz[N], lll, tag[N << 3];

long long n, val[N], m, a, b, c, op;

void push_down(long long u, long long l, long long r)

{

	sum[u << 1ll] += tag[u] * (mid - l + 1);

	sum[(u << 1ll) + 1ll] += tag[u] * (r - mid);

	tag[u << 1ll] += tag[u];

	tag[(u << 1ll) + 1ll] += tag[u];

	sum[u] = sum[u << 1ll] + sum[(u << 1ll) + 1ll];

	tag[u] = 0;

	return;

}

void build(long long root, long long l, long long r)

{

	if (l == r)

	{

		sum[root] = val[wz[l]];

		return;

	}

	build(root << 1ll, l, mid);

	build((root << 1ll) + 1ll, mid + 1ll, r);

	sum[root] = sum[root << 1ll] + sum[(root << 1ll) + 1ll];

	return;

}

void update(long long root, long long l, long long r, long long x, long long k)

{

	push_down(root, l, r);

	if(l == r)

	{

		sum[root] += k;

		return;

	}

	if (x > mid)

		update((root << 1ll) + 1ll, mid + 1ll, r, x, k);

	else

		update(root << 1ll, l, mid, x, k);

	sum[root] = sum[root << 1ll] + sum[(root << 1ll) + 1ll];

	return;

}

void update(long long root, long long l, long long r, long long x, long long y, long long k)

{

	if(l >= x && r <= y)

	{

		tag[root] += k;

		return;

	}

	push_down(root, l, r);

	if (y > mid)

		update((root << 1ll) + 1ll, mid + 1ll, r, x, y, k);

	if (x <= mid)

		update(root << 1ll, l, mid, x, y, k);

	sum[root] = sum[root << 1ll] + sum[(root << 1ll) + 1ll];

	return;

}

long long query(long long root, long long l, long long r, long long qx, long long qy)

{

	push_down(root, l, r);

	if (l >= qx && r <= qy)

		return sum[root];

	if (l == r)

		return 0;

	long long u = 0, v = 0;

	if (mid >= qx)

		u = query(root << 1ll, l, mid, qx, qy);

	if (qy > mid)

		v = query((root << 1ll) + 1ll, mid + 1ll, r, qx, qy);

	return u + v;

}

long long query_sum(long long x)

{

	long long ans = 0;

	while (top[x] != 1)

	{

		ans += query(1ll, 1ll, n, dfn[top[x]], dfn[x]);

		x = f[top[x]];

	}

	ans += query(1ll, 1ll, n, 1ll, dfn[x]);

	return ans;

}

void dfs1(long long x, long long fa)

{

	f[x] = fa;

	dep[x] = dep[fa] + 1;

	size[x] = 1;

	for (auto i : e[x])

	{

		if (i == fa)

			continue;

		dfs1(i, x);

		size[x] += size[i];

		if(size[son[x]] < size[i] )

			son[x] = i;

	}

	return;

}

void dfs2(long long x, long long t)

{

	dfn[x] = ++lll;

	wz[lll] = x;

	top[x] = t;

	if (!son[x])

		return;

	dfs2(son[x], t);

	for(auto i : e[x])

	{

		if (i == f[x] || i == son[x])

			continue;

		dfs2(i, i);

	}

}

int main()

{

	cin >> n >> m;

	for (long long i = 1ll; i <= n; i++)

		scanf("%lld", val + i);

	for (long long i = 1, u, v; i < n; i++)

	{

		scanf("%lld%lld", &u, &v);

		e[u].push_back(v);

		e[v].push_back(u);

	}

	dfs1(1ll, 0ll);

	dfs2(1ll, 1ll);

	build(1ll, 1ll, n);

	while (m--)

	{

		scanf("%lld%lld", &op, &a);

		if (op == 1ll)

		{

			scanf("%lld", &b);

			update(1ll, 1ll, n, dfn[a], b);

		}

		else if (op == 2ll)

		{

			scanf("%lld", &b);

			update(1ll, 1ll, n, dfn[a], dfn[a] + size[a] - 1ll, b);

		}

		else

		{

			cout << query_sum(a) << "\n";

		}

	}

}