题解 P6185 【[NOI Online 提高组]序列（民间数据）】

xht · 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;
}