题解 P6185 【[NOI Online 提高组]序列（民间数据）】
xht
2020-03-07 21:41:31
把每个位置看成一个点。
首先对于 $2$ 操作连边。
如果两个位置连通则意味着可以使一个位置 $+1$ 另一个位置 $-1$。
即对于一个连通块，我们可以在保证**总和**不变的情况下任意的加减，因此并查集将一个连通块缩成一个点。
再对于 $1$ 操作连边。
如果形成的图是二分图，则可以在保证**左部点总和与右部点总和的差**不变的情况下任意的加减。
如果形成的图不是二分图，则可以在保证**总和奇偶性**不变的情况下任意的加减。
```cpp
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;
}
```