P9424 [Lanqiao Cup 2023 National B] Edge Deletion Problem

Given an undirected graph $G$ with $N$ nodes and $M$ edges, where the nodes are numbered $1 \cdots N$. Each node has a weight $W_i$. You may choose exactly one edge from the $M$ edges and delete it. If the remaining graph contains exactly $2$ connected components, then this is called a valid deletion plan. For a valid deletion plan, suppose the sums of node weights in the two connected components are $X$ and $Y$, respectively. Please find a plan that makes the difference between $X$ and $Y$ as small as possible, and output the difference between $X$ and $Y$.

The first line contains two integers $N$ and $M$. The second line contains $N$ integers $W_1, W_2, \cdots, W_N$. The following $M$ lines each contain two integers $U$ and $V$, indicating that there is an edge between node $U$ and node $V$.

Output one integer representing the minimum difference. If there is no valid deletion plan, output $-1$.

### Sample Explanation Since there are actually $2$ edges between $1$ and $2$, there are $2$ valid deletion plans: deleting the edge between $(2, 3)$ and deleting the edge between $(3, 4)$. If we delete the edge between $(2, 3)$, the remaining graph contains $2$ connected components: $\{1,2\}$ and $\{3,4\}$. Their weight sums are $30$ and $70$, and the difference is $40$. If we delete the edge between $(3, 4)$, the remaining graph contains $2$ connected components: $\{1,2,3\}$ and $\{4\}$. Their weight sums are $60$ and $40$, and the difference is $20$. ### Constraints and Notes for Test Cases - For $20\%$ of the testdata, $1 \le N, M \le 10000$. - For another $20\%$ of the testdata, the degree of each node is at most $2$. - For $100\%$ of the testdata, $1 \le N, M \le 200000$, $0 \le W_i \le 10^9$, $1 \le U, V \le N$. The 14th Lanqiao Cup Software Contest Finals, C/C++ College Group B, Problem F. Translated by ChatGPT 5