No.3720 Balanced Reduction
Problem Statement
You are given positive integers $N, K$, a sequence $A$ of $N$ non-negative integers, and a simple connected undirected graph with $N$ vertices and $N$ edges. The vertices are numbered $1,2,\dots,N$, and the non-negative integer $A_i$ is written on vertex $i$.
You may perform the following operation any number of times.
- Choose an edge and an integer $x$ satisfying $K \le x \le 2K$, and decrease the integers written on the $2$ vertices directly connected by that edge by $x$ each.
Determine whether it is possible to make the integers written on all vertices $0$, and if it is possible, find the minimum number of operations required to do so.
Constraints
- All input values are integers.
- $3 \le N \le 2 \times 10^5$
- $2 \le K \le 10^9$
- $0 \le A_i \le 10^9$ $(1 \le i \le N)$
- $1 \le u_i,v_i \le N$ $(1 \le i \le N)$
- The given graph is simple.
- The given graph is connected.
Input
The input is given from Standard Input in the following format.
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_N$ $v_N$
Output
Output the minimum number of operations required to make the integers written on all vertices $0$.
If it is impossible, output -1.
Sample
Sample 1
Input
5 2 2 7 6 3 0 1 2 2 3 3 1 2 4 3 5
Output
3
For example, by choosing the edges $(2,3),(3,1),(2,4)$ and operating with $x=4,2,3$ respectively, you can make the integers written on all vertices $0$.
Sample 2
Input
4 3 3 3 6 6 1 2 2 3 3 4 4 1
Output
2
You can operate with $x=3$ on edge $(1,2)$ and $x=6$ on edge $(3,4)$.
Sample 3
Input
3 2 10 10 10 1 2 2 3 3 1
Output
6
The same edge may be chosen multiple times.
Sample 4
Input
3 3 6 8 10 1 2 2 3 3 1
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ぽえ
kazuppa