問題一覧 > 通常問題

No.1911 Alternately Coloring

レベル : / AI推定難易度 : 2225 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 23
作問者 : chineristAC / テスター : 👑 hamamu tokusakurai
お気に入りにしたユーザー ProblemId : 7294 / 自分の提出
問題文最終更新日: 2022-04-12 23:28:53
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 340 (順位表) の他の問題:

Problem Statement

There is a simple connected undirected graph with $N$ vertices and $M$ edges. The $i\ (1\le i \le M)$-th edge connects vertices $u_i,\ v_i$.

Initially, none of the $N$ vertices are colored. chinerist is going to paint each vertex red or blue in the following way.

First, he chooses any vertex, paints it either red or blue as he likes, and places a piece on it.

Next, he performs the following operation $0$ or more times.

Operation
  • Let $i$ be the vertex on which the piece is currently placed. Choose $1$ vertex $j$ connected to vertex $i$ by an edge. Paint vertex $j$ with the color, out of red and blue, that differs from the color of vertex $i$ (if it is already colored, the color is overwritten), and move the piece to vertex $j$.

After he finishes the operations, for each vertex $i\ (1 \le i \le N)$, he gains $R_i$ points if it is painted red, $B_i$ points if it is painted blue, and $0$ points if it is not colored.

Find the maximum number of points he can obtain after finishing the operations, when he performs them appropriately.

Input

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$R_1$ $R_2$ $\dots$ $R_N$
$B_1$ $B_2$ $\dots$ $B_N$
  • $2 \le N \le 1000$
  • $N-1 \le M \le \min(\frac{N(N-1)}{2},1000)$
  • $1 \le u_i < v_i \le N$
  • $1 \le R_i,\ B_i \le 10^9$
  • All input values are integers.
  • The given graph is a simple connected undirected graph.

Output

Output the answer.

Print a newline at the end.

Sample

Sample 1
Input
3 3
1 2
2 3
1 3
1 2 3
4 3 5
Output
11

If he places the piece on vertex $1$, paints vertex $1$ blue, and then moves the piece in the order vertex $1\rightarrow$ vertex $2\rightarrow$ vertex $3$, vertices $1,\ 2,\ 3$ can be painted blue, red, and blue, respectively. In this case, $4+2+5=11$ points are obtained.

Sample 2
Input
15 20
2 14
1 12
10 11
9 12
4 12
3 8
7 11
1 2
11 14
7 9
14 15
2 6
6 10
3 4
10 13
9 15
5 15
5 8
5 13
3 6
77 109 121 121 163 117 125 149 82 136 81 130 125 102 106
166 39 46 43 69 63 51 57 5 38 14 33 71 29 35
Output
1712

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