Figure Fixing (Codeforces 1537F)
Tags: Math, dsu

You have a connected undirected graph made of $$$n$$$ nodes and $$$m$$$ edges. The $$$i$$$-th node has a value $$$v_i$$$ and a target value $$$t_i$$$.In an operation, you can choose an edge $$$(i, j)$$$ and add $$$k$$$ to both $$$v_i$$$ and $$$v_j$$$, where $$$k$$$ can be any integer. In particular, $$$k$$$ can be negative.Your task to determine if it is possible that by doing some finite number of operations (possibly zero), you can achieve for every node $$$i$$$, $$$v_i = t_i$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$), the number of test cases. Then the test cases follow.The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$, $$$n-1\leq m\leq \min(2\cdot 10^5, \frac{n(n-1)}{2})$$$) — the number of nodes and edges respectively.The second line contains $$$n$$$ integers $$$v_1\ldots, v_n$$$ ($$$-10^9 \leq v_i \leq 10^9$$$) — initial values of nodes.The third line contains $$$n$$$ integers $$$t_1\ldots, t_n$$$ ($$$-10^9 \leq t_i \leq 10^9$$$) — target values of nodes.Each of the next $$$m$$$ lines contains two integers $$$i$$$ and $$$j$$$ representing an edge between node $$$i$$$ and node $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i\ne j$$$).It is guaranteed that the graph is connected and there is at most one edge between the same pair of nodes.It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$m$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, if it is possible for every node to reach its target after some number of operations, print "YES". Otherwise, print "NO".

Note: Here is a visualization of the first test case (the orange values denote the initial values and the blue ones the desired values):   One possible order of operations to obtain the desired values for each node is the following:  Operation $$$1$$$: Add $$$2$$$ to nodes $$$2$$$ and $$$3$$$.  Operation $$$2$$$: Add $$$-2$$$ to nodes $$$1$$$ and $$$4$$$.  Operation $$$3$$$: Add $$$6$$$ to nodes $$$3$$$ and $$$4$$$. Now we can see that in total we added $$$-2$$$ to node $$$1$$$, $$$2$$$ to node $$$2$$$, $$$8$$$ to node $$$3$$$ and $$$4$$$ to node $$$4$$$ which brings each node exactly to it's desired value.For the graph from the second test case it's impossible to get the target values.

Sample Inputs:
2
4 4
5 1 2 -3
3 3 10 1
1 2
1 4
3 2
3 4
4 4
5 8 6 6
-3 1 15 4
1 2
1 4
3 2
3 4

Sample Outputs:
YES
NO

Solution (Python):
import itertools

def is_digraph(edges):
    n = len(edges)
    color = [None] * n
    color[0] = 1
    q = [0]
    while q:
        pos = q.pop()
        c = 1 - color[pos]
        for nxt in edges[pos]:
            if color[nxt] is None:
                color[nxt] = c
                q.append(nxt)
            elif color[nxt] != c:
                return (False, None)
    return (True, color)

def solve():
    (n, m) = map(int, input().split())
    v = list(map(int, input().split()))
    t = list(map(int, input().split()))
    edges = [list() for __ in range(n)]
    parity = 0
    for __ in range(m):
        (i, j) = map(int, input().split())
        i -= 1
        j -= 1
        edges[i].append(j)
        edges[j].append(i)
    for x in itertools.chain(v, t):
        parity ^= x & 1
    if parity:
        print('NO')
        return
    (di, colors) = is_digraph(edges)
    if not di:
        print('YES')
    else:
        sums = [0, 0]
        for (i, c) in enumerate(colors):
            sums[c] += t[i] - v[i]
        (a, b) = sums
        print('YES') if a == b else print('NO')
for testcases in range(int(input())):
    solve()

Solution (Python):
import itertools

def is_digraph(edges):
    n = len(edges)
    color = [None] * n
    color[0] = 1
    q = [0]
    while q:
        pos = q.pop()
        c = 1 - color[pos]
        for nxt in edges[pos]:
            if color[nxt] is None:
                color[nxt] = c
                q.append(nxt)
            elif color[nxt] != c:
                return (False, None)
    return (True, color)

def solve():
    (n, m) = map(int, input().split())
    v = list(map(int, input().split()))
    t = list(map(int, input().split()))
    edges = [list() for __ in range(n)]
    parity = 0
    for __ in range(m):
        (i, j) = map(int, input().split())
        i -= 1
        j -= 1
        edges[i].append(j)
        edges[j].append(i)
    for x in itertools.chain(v, t):
        parity ^= x & 1
    if parity:
        print('NO')
        return
    (di, colors) = is_digraph(edges)
    if not di:
        print('YES')
    else:
        sums = [0, 0]
        for (i, c) in enumerate(colors):
            sums[c] += t[i] - v[i]
        (a, b) = sums
        print('YES') if a == b else print('NO')
for testcases in range(int(input())):
    solve()

Solution (Python):
import itertools

def is_digraph(edges):
    n = len(edges)
    color = [None] * n
    color[0] = 1
    q = [0]
    while q:
        pos = q.pop()
        c = 1 - color[pos]
        for nxt in edges[pos]:
            if color[nxt] is None:
                color[nxt] = c
                q.append(nxt)
            elif color[nxt] != c:
                return (False, None)
    return (True, color)

def solve():
    (n, m) = map(int, input().split())
    v = list(map(int, input().split()))
    t = list(map(int, input().split()))
    edges = [list() for __ in range(n)]
    for __ in range(m):
        (i, j) = map(int, input().split())
        i -= 1
        j -= 1
        edges[i].append(j)
        edges[j].append(i)
    parity = 0
    for x in itertools.chain(v, t):
        parity ^= x & 1
    if parity:
        print('NO')
        return
    (di, colors) = is_digraph(edges)
    if not di:
        print('YES')
    else:
        sums = [0, 0]
        for (i, c) in enumerate(colors):
            sums[c] += t[i] - v[i]
        (a, b) = sums
        print('YES') if a == b else print('NO')

def main():
    t = int(input())
    for __ in range(t):
        solve()
if __name__ == '__main__':
    main()