問題一覧 > 通常問題

No.3720 Balanced Reduction

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : ぽえ / テスター : kazuppa 👑 loop0919
お気に入りにしたユーザー ProblemId : 14045 / 自分の提出
問題文最終更新日: 2026-09-18 21:22:00
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 514 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。