问题陈述
(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。