CF1537F Figure Fixing
Description
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 Format
N/A
Output Format
N/A
Explanation/Hint
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.