CF1220E Tourism

Alex 决定进行一次全国旅游。 为简化问题，假设该国家有 $n$ 个城市和 $m$ 条双向道路连接这些城市。Alex 住在城市 $s$，最初位于该城市。为了比较不同的城市，Alex 给每个城市分配了一个分数 $w_i$，分数越高表示该城市对 Alex 越有吸引力。 Alex 认为，只有在旅行过程中不连续重复走同一条道路，他的旅行才会有趣。也就是说，如果 Alex 从城市 $u$ 来到城市 $v$，那么他可以选择下一个通过道路与 $v$ 相连的任意城市，但不能回到城市 $u$。 你的任务是帮助 Alex 规划他的旅行路线，使他所访问过的所有城市的总分数最大。注意，每个城市的分数最多只能计入一次，即使 Alex 在旅行中多次到达该城市。

输入的第一行包含两个整数 $n$ 和 $m$，表示该国家的城市数和道路数（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$0 \le w_i \le 10^9$），分别表示每个城市的分数。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示一条连接城市 $u$ 和城市 $v$ 的道路。 保证任意两座城市之间最多只有一条直接道路，没有城市通过道路与自身相连，并且从任意一座城市出发都可以通过道路到达其他任意城市。 最后一行包含一个整数 $s$（$1 \le s \le n$），表示起始城市的编号。

输出一个整数，表示 Alex 能够访问到的城市分数之和的最大值。

由 ChatGPT 4.1 翻译