自动搬运

查看原文

来自洛谷，原作者为

	tjtdrxxz 要是把博士抬去寝室，会不会被人误会啊？干脆就这样子放着好了......？

搬运于2025-08-24 22:42:54，当前版本为作者最后更新于2024-09-22 12:14:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先看题：

1. 操作一，删除编号为 $e_i$ 的边。
2. 操作二，把编号为 $u_i$ 的点的权值改成 $v_i$。
3. 操作三，询问编号为 $u_i$ 的点所在的子树的权值和。

很明显，如果没有操作一，这提示能用并查集吊打的。但是他是绿题，所以有操作一。

因为初始时是一棵树，所以在删除一些边后他就是森林了。好，那这题就能用 LCT 并查集切掉。

因为正着来的话删边会很麻烦，所以先离线，然后倒着来。这样删边就转化成了连接 $u$ 和 $v$，把 $u$ 的点权改成 $v$ 就变成了把 $u$ 的点权改成上一次操作的 $v$，询问子树和可以用并查集维护。因为是倒着来的，所以输出答案时可以用一个栈存储。

warning：合并时要注意，一般的并查集都是这样写的 fa[find (u)] = find (v);，所以合并子树和的时候是 sum[find (v)] += sum[find (u)];。

注意一下下标之类的细节就好了，代码还是很容易实现的。

code：

# include "bits/stdc++.h"
# define int long long
using namespace std;
namespace chtholly
{
	template <const int N>
	class UFDS
	{
		private :
			int s[N];
			int a[N];
			int fa[N];
		public :
			int find (int u)
			{
				return u == fa[u] ? u : fa[u] = find (fa[u]);
			}
			void merge (int u, int v)
			{
				u = find (u);
				v = find (v);
				if (u != v)
				{
					fa[u] = v;//这里是把子树 u 合并到 v 上，所以合并子树和的时候是如下写法。
					s[v] += s[u];
				}
			}//合并。
			void init ()
			{
				for (int i = 1; i < N; i ++) fa[i] = i;
			}//初始化。
			int sum (int u)
			{
				return s[find (u)];
			}//子树和。
			void change (int u, int x)
			{
				int f = find (u);
				s[f] += x - a[u];
				a[u] = x;
			}//单点修改，因为是把点 u 的值改成 x，所以把子树和加上 x 再减去 u 本身的值就好了。
	};//以上为并查集
}
using namespace chtholly;
# define stdi stdin
# define stdo stdout
UFDS <100012> tree;
int n, m, a[100012];
bool f[100012];
int u[100012], v[100012], last[100012];
int op[100012], x[100012], y[100012];
signed main ()
{
	cin >> n >> m;
	tree.init ();
	for (int i = 1; i <= n; i ++)
	{
		int num; cin >> num;
		a[i] = num;
	}
	for (int i = 1; i < n; i ++)
	{
		cin >> u[i] >> v[i];
		f[i] = 1;
	}
	for (int i = 1; i <= m; i ++)
	{
		cin >> op[i] >> x[i];
		if (op[i] == 1) f[x[i]] = 0;
		if (op[i] == 2)
		{
			cin >> y[i];
			tree.change (x[i], y[i]);
			last[i] = a[x[i]]; //记录上一次的操作后的值。
			a[x[i]] = y[i];
		}
	}
	for (int i = 1; i <= n; i ++) tree.change (i, a[i]);
	for (int i = 1; i < n; i ++)
	{
		if (f[i])
		{
			tree.merge (u[i], v[i]);
		}
	}
//	cout << "sum : ";
//	for (int i = 1; i <= n; i ++) cout << tree.sum (i) << ' ';
//	cout << endl;
	vector <int> q;
	for (int i = m; i >= 1; i --)
	{
		if (op[i] == 1) tree.merge (u[x[i]], v[x[i]]);
		if (op[i] == 2) tree.change (x[i], last[i]);
		if (op[i] == 3) q.push_back (tree.sum (x[i]));
	}
	while (not q.empty ()) cout << q.back () << endl, q.pop_back ();
}