题意

有一颗树，每个点有一个点权 \(v\)。现在要对这棵树进行 \(m\) 次以下三种操作之一：

• 删除一条边。

• 修改一个点的点权。

• 查询一个点 \(u\) 所在的树的点权之和。

解题思路

这道题并没有要求在线，容易想到离线倒序操作的想法。

我们先把所有操作进行完之后的情景模拟出来，由于是倒序操作，只有加边没有删边，所以我们用并查集维护。接下来，对于三种操作，我们进行如下操作：

• 对于第一种操作，我们将点的两个端点所在的树合并。

• 对于第二种操作，我们将这棵树的点权之和加上原来的点权再减去现在的点权。

• 对于第三种操作，我们直接将这个点所在的树的点权之和压入答案数组即可。

代码实现

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int opt, e, val, u;
} q[100001];
struct _
{
	int x, y;
} e[100001];
int n, m, sum[100001], fa[100001], ans[100001], tot;
stack<int> change[100001];
bool del[100001];
int find(int x)
{
	if (x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++) scanf("%d", &sum[i]), change[i].push(sum[i]), fa[i] = i;
	for (int i = 1; i < n; i ++) scanf("%d%d", &e[i].x, &e[i].y);
	for (int i = m; i >= 1; i --)
	{
		scanf("%d", &q[i].opt);
		if (q[i].opt == 1)
		{
			scanf("%d", &q[i].e);
			del[q[i].e] = true;
		}
		else if (q[i].opt == 2) 
		{
			scanf("%d%d", &q[i].u, &q[i].val);
			sum[q[i].u] = q[i].val;
			change[q[i].u].push(q[i].val);
		}
		else scanf("%d", &q[i].u);
	}
	for (int i = 1; i < n; i ++)
		if (!del[i])
		{
			int fx = find(e[i].x), fy = find(e[i].y);
			fa[fy] = fx;
			sum[fx] += sum[fy];
		}
	for (int i = 1; i <= m; i ++)
	{
		if (q[i].opt == 1)
		{
			int fx = find(e[q[i].e].x), fy = find(e[q[i].e].y);
			fa[fy] = fx;
			sum[fx] += sum[fy];
		}
		else if (q[i].opt == 2)
		{
			int fx = find(q[i].u), tmp = change[q[i].u].top();
			change[q[i].u].pop();
			sum[fx] += change[q[i].u].top() - tmp;
		}
		else
		{
			int fx = find(q[i].u);
			ans[++ tot] = sum[fx];
		}
	}
	for (int i = tot; i >= 1; i --) printf("%d\n", ans[i]);
	return 0;
}