自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:18:19，当前版本为作者最后更新于2020-03-07 21:41:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

把每个位置看成一个点。

首先对于 $2$ 操作连边。

如果两个位置连通则意味着可以使一个位置 $+1$ 另一个位置 $-1$。

即对于一个连通块，我们可以在保证总和不变的情况下任意的加减，因此并查集将一个连通块缩成一个点。

再对于 $1$ 操作连边。

如果形成的图是二分图，则可以在保证左部点总和与右部点总和的差不变的情况下任意的加减。

如果形成的图不是二分图，则可以在保证总和奇偶性不变的情况下任意的加减。

const int N = 1e5 + 7;
int n, m, a[N], b[N], f[N], p[N], q[N], t, v[N];
ll s[N], c[3];
vi e[N];

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

inline bool dfs(int x, int k) {
	v[x] = k, c[k] += s[x];
	bool ok = 1;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (v[y] == v[x]) ok = 0;
		if (!v[y] && !dfs(y, 3 - k)) ok = 0;
	}
	return ok;
}

inline bool solve() {
	rd(n), rd(m), rda(a, n), rda(b, n), t = 0;
	for (int i = 1; i <= n; i++) f[i] = i, s[i] = v[i] = 0, e[i].clear();
	for (int i = 1, o, x, y; i <= m; i++) {
		rd(o), rd(x), rd(y);
		if (o == 2) f[get(x)] = get(y);
		else p[++t] = x, q[t] = y;
	}
	for (int i = 1; i <= n; i++) s[get(i)] += b[i] - a[i];
	for (int i = 1; i <= t; i++) {
		int x = get(p[i]), y = get(q[i]);
		e[x].pb(y), e[y].pb(x);
	}
	for (int i = 1; i <= n; i++)
		if (get(i) == i && !v[i]) {
			c[1] = c[2] = 0;
			bool ok = dfs(i, 1);
			if (ok && c[1] != c[2]) return 0;
			if (!ok && ((c[1] ^ c[2]) & 1)) return 0;
		}
	return 1;
}

int main() {
	int T;
	rd(T);
	while (T--) prints(solve() ? "YES" : "NO");
	return 0;
}