自动搬运

查看原文

来自洛谷，原作者为

	chenly8128 God helps those who help themselves.

搬运于2025-08-24 23:00:01，当前版本为作者最后更新于2025-03-30 12:51:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

预备知识

• 动态树 LCT
• 并查集

思路

由于一个点可以多次经过，但是每一条边方向必须是固定的，所以可以自然的想到边双连通分量。

每到达一个边双连通分量，可以在这个边双连通分量中转圈。这样同一个边双连通分量之中的所有点一定都可以到达。

因此我们可以直接缩点，缩点后的权值为所有点本来值的总和。缩完点的无向图是森林。

然后这就变成了一道用动态树维护双连通分量的题目。缩点我们可以使用并查集。

具体实现

由于我们使用了并查集，所以在标准动态树的基础上，还需要进行略微改动。

具体来说：

1. 在 access 函数中改动一下。每次向上移动前，将父亲节点设为父亲节点所在并查集的根。

2. 新增函数 dfs 来实现对于整条实链缩点这一功能。

然后再来说题目的三种询问操作：

1. 对于操作 1：先用 find_root 函数判断 A 和 B 是否连通。如果不连通直接将它们连起来；否则将这两个点之间的实链分离出来，整条实链缩点。

2. 对于操作 2：先令 C 为 A 节点所在的并查集的根，把这个 C make_root(C) 成整棵树的根，最后更新 C 的权值。为了更新 C 的权值，需要记录每个节点目前的权值，通过变化的差值进行更新。

3. 对于操作 3：先判断是否连通，如果连通就分离 A 和 B 之间的实链，输出实链权值和。否则输出 -1。

如果将并查集复杂度当作常数，那么总复杂度为 $O(q \log_2 n)$。

代码

// Author: chenly8128
// Created: 2025-03-21 20:57:47

#include <bits/stdc++.h>
using namespace std;
inline int read (void) {
	int res = 0;bool flag = true;char c = getchar();
	while (c < '0' || c > '9') {flag ^= (c == '-');c = getchar();}
	while (c >= '0' && c <= '9') {res = (res << 3) + (res << 1) + (c ^ 48);c = getchar();}
	return flag ? res : -res;
}
const int MAXN = 2e5+10;
int fa[MAXN],cnt[MAXN];
int find (int x) {
	return fa[x] = fa[x] == x ? x : find(fa[x]);
}
void merge (int a,int b) {
	a = find(a);b = find(b);
	if (a == b) return;
	fa[a] = b;
	cnt[b] += cnt[a];
}
struct LCT {
	int sum[MAXN],ch[MAXN][2],fa[MAXN],tot;
	bool lazy[MAXN];
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
	inline int dir (int fa,int x) {return ls(fa) == x ? 0 : 1;}
	inline bool isroot (int x) {return ls(fa[x]) != x && rs(fa[x]) != x;}
	inline void push_up (int x) {sum[x] = sum[ls(x)] + sum[rs(x)] + cnt[x];}
	inline void reverse (int x) {if (x) {swap(ls(x),rs(x));lazy[x] ^= true;}}
	inline void push_down (int x) {
		if (lazy[x]) {
			reverse(ls(x));
			reverse(rs(x));
			lazy[x] = false;
		}
	}
	void push (int x) {
		if (!isroot(x)) push(find(fa[x]));
		push_down(x);
	}
	void rotate (int x) {
		if (isroot(x)) return;
		int y = fa[x]; int z = fa[y],r = dir(y,x);
		ch[y][r] = ch[x][r^1];
		ch[x][r^1] = y;
		if (!isroot(y)) ch[z][dir(z,y)] = x;
		if (ch[y][r]) fa[ch[y][r]] = y;
		fa[x] = z;
		fa[y] = x;
		push_up(y);
		push_up(x);
	}
	void splay (int x) {
		push(x);
		int y,z;
		while (!isroot(x)) {
			y = fa[x];z = fa[y];
			if (!isroot(y)) rotate(dir(z,y) == dir(y,x) ? y : x);
			rotate(x);
		}
		push_up(x);
	}
	void access (int y) {
		for (int x = 0;y;x = y,y = fa[x] = find(fa[x])) {
			splay(y);
			rs(y) = x;
			push_up(y);
		}
	}
	void make_root (int x) {
		access(x);splay(x);reverse(x);
	}
	int find_root (int x) {
		access(x);splay(x);
		while (ls(x)) {
			push_down(x);
			x = ls(x);
		}
		splay(x);
		return x;
	}
	void split(int x,int y) {
		make_root(x);
		access(y);
		splay(y);
	}
	void link (int x,int y) {
		make_root(x);make_root(y);
		fa[x] = y;
	}
	void dfs (int x,int rt) {
		merge(x,rt);
		if (ls(x)) dfs(ls(x),rt);
		if (rs(x)) dfs(rs(x),rt);
		ls(x) = rs(x) = 0;
	}
} a;

int n,m,tmp[MAXN];
int op,x,y;
int main (void) {
	n = read(); m = read();
	for (int i = 1;i <= n;i++) {
		tmp[i] = cnt[i] = read();
		fa[i] = i;
	}
	while (m--) {
		op = read(); x = read(); y = read();
		if (op == 2) {
			int p = find(x);
			a.make_root(p);
			cnt[p] += y-tmp[x];
			tmp[x] = y;
			a.push_up(p);
		}
		else {
			x = find(x); y = find(y);
			if (op == 1) {
				if (a.find_root(x) != a.find_root(y)) a.link(x,y);
				else {
					a.split(x,y);
					a.dfs(y,y);
					a.push_up(y);
				}
			}
			else {
				if (a.find_root(x) != a.find_root(y)) printf ("-1\n");
				else {
					a.split(x,y);
					printf ("%d\n",a.sum[y]);
				}
			}
		}
	}
	return 0;
}