← 返回题目列表

Codeforces · 1220/E

E. 旅游

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

亚历克斯决定去全国各地旅游。

为简单起见,我们假设该国家有 $$$n$$$ 个城市和连接它们的 $$$m$$$ 双向道路。亚历克斯住在城市 $$$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$$$ 行包含道路的描述。每条 $$$m$$$ 行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),它们是这条道路连接的城市。

保证任意两个城市之间至多有一条直达道路,没有城市通过道路与自身相连,最后,可以仅通过道路从任何城市前往任何其他城市。

最后一行包含单个整数$$$s$$$ ($$$1 \le s \le n$$$),它是初始城市的编号。

输出

输出单个整数,它是访问过的城市的最大可能得分总和。

示例

输入 #1

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

输出 #1

27

输入 #2

10 12
1 7 1 9 3 3 6 30 1 10
1 2
1 3
3 5
5 7
2 3
5 4
6 9
4 6
3 7
6 8
9 4
9 10
6

输出 #2

61