← 返回题目列表

AtCoder · icpc2015summer_day2_g

G. 逃脱

中文机器翻译题面 查看原题

问题陈述

(13:35) 部分修正了输入格式的描述

给出了顶点为正值的无向图。 从1到顶点 它的编号为 N 。 第i 个顶点是 它的值为 w_i 。 从第一个顶点开始,您可以在图形中移动,但约束不能穿过最后一条边。 对于每个顶点,只有当您第一次访问该顶点时,您才能获得该顶点的值的积分。

求可获得的总点数的最大值。


约束

  • 1 \leq N \leq 100000
  • N-1 \leq M \leq 100000
  • 1 \leq w_i \leq 1000
  • 1 \leq u_i, v_i \leq N
  • 不存在重边或自边。
  • 图已连接

输入格式

输入是按以下格式从标准输入给出的。
N M
w_1 w_2 ... w_N
u_1 v_1
u_2 v_2
...
u_M v_M

1 在线图表(13:36:00修改)中的顶点数 N 和表示边数的整数 输入 M 。
2 每个顶点的值 w_i 。
继续 M 通过每条边连接到行 2 输入顶点编号。

输出格式

将您的答案打印在一行上。

示例输入 1

6 6
1 2 3 4 5 6
1 2
2 3
3 4
1 4
4 5
5 6

示例输出 1

21

您可以从顶点 1 → 2 → 3 → 4 → 5 → 6 开始收集所有顶点的点。

示例输入 2

7 8
1 3 3 5 2 2 3
1 2
2 3
3 1
1 4
1 7
1 5
1 6
5 6

示例输出 2

16

顶点 您可以通过以下步骤收集 16 个点:1 → 2 → 3 → 1 → 5 → 6 → 1 → 4。