問題一覧 > 通常問題

No.3781 Erase One, Gain from the Other

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 17
作問者 : askr58 / テスター : 👑 AngrySadEight / テストしたAI : claude-opus-5-5
お気に入りにしたユーザー ProblemId : 13590 / 自分の提出
問題文最終更新日: 2026-10-30 20:36:56
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 520 (順位表) の他の問題:

Problem Statement

There is an undirected graph with $N$ vertices and $M$ edges. The vertices are numbered with integers from $1$ to $N$, and the edges are numbered with integers from $1$ to $M$. For $1\le i \le M$, edge $i$ connects vertex $u_i$ and vertex $v_i$ bidirectionally. Each vertex also has a non-negative integer weight, and for $1\le i\le N$, the weight of vertex $i$ is $A_i$.

Initially, no vertex is painted black. Consider the following operation.

  • Choose $1$ pair $(u,v)$ of $2$ vertices such that neither of them is painted black and they are directly connected by an edge. Paint $u$ black and gain $A_v$ yen.

Note that since every edge is undirected, whenever the operation is possible for the pair $(u,v)$, it is also possible for the pair $(v,u)$.

What is the maximum possible total amount of money that can be gained by performing this operation any number of times, $0$ or more?

Solve $T$ test cases.

Constraints

  • $1\le T\le 2\times 10^5$
  • $1\le N\le 2\times 10^5$
  • $0\le M\le 2\times 10^5$
  • $1\le u_i < v_i\le N\ (1\le i\le M)$
  • $(u_i,v_i) \neq (u_j,v_j)\ (1\le i < j\le M)$
  • $0\le A_i\le 10^9\ (1\le i\le N)$
  • The sum of $N$ and the sum of $M$ over the $T$ test cases are each at most $2\times 10^5$
  • All input values are integers

Input

The input is given in the following format, where $case_i$ represents the $i$-th test case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format.

$N\ M$
$A_1\ A_2\ \cdots\ A_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$

Output

Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

Sample

Sample 1
Input
2
6 7
7 2 3 1 3 6
1 2
1 3
2 4
3 4
3 5
4 6
5 6
10 13
4 9 0 6 7 1 5 9 3 7
1 6
1 7
1 9
2 4
2 9
3 7
3 9
5 10
6 7
6 8
6 9
8 9
9 10
Output
26
52

In test case $1$, you can gain $26$ yen by performing the operations as follows.

  • Perform the operation on $(2,1)$. You gain $7$ yen.
  • Perform the operation on $(3,1)$. You gain $7$ yen.
  • Perform the operation on $(4,6)$. You gain $6$ yen.
  • Perform the operation on $(5,6)$. You gain $6$ yen.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。