P1453 城市环路 - 洛谷 与 [[P2607 骑士 - 洛谷]]也是有关联。 # 城市环路
题目描述
一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。
B 市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕 B 市的环路，环路之内便是 B 市中心。
整个城市可以看做一个 \(n\) 个点，\(n\) 条边的单圈图（保证图连通），唯一的环便是绕城的环路。保证环上任意两点有且只有 \(2\) 条简单路径互通。图中的其它部分皆隶属城市郊区。
现在，有一位名叫 Jim 的同学想在 B 市开店，但是任意一条边的 \(2\) 个点不能同时开店，每个点都有一定的人流量，第 \(i\) 个点的人流量是 \(p_i\)，在该点开店的利润就等于 \(p_i×k\)，其中 \(k\) 是一个常数。
Jim 想尽量多的赚取利润，请问他应该在哪些地方开店？
输入格式
\(\boxed{\begin{align}&n\\&a_{1}&a_{2}&&\dots&&a_{n}\\&u_{1}&v_{1}\\&u_{2}&v_{2}\\&\vdots\\&u_{n}&v_{n}\\&k\end{align}}\) 第一行一个整数 \(n\)，代表城市中点的个数。城市中的 \(n\) 个点由 \(0 \sim n-1\) 编号。 第二行有 \(n\) 个整数，第 \((i + 1)\) 个整数表示第 \(i\) 个点的人流量 \(p_i\)。 接下来 \(n\) 行，每行有两个整数 \(u, v\)，代表存在一条连接 \(u\) 和 \(v\) 的道路。 最后一行有一个实数，代表常数 \(k\)。 (点从 0 开始) 数据范围： \(1 \leq n \leq 10^5\)，\(1 \leq p_i \leq 10^4\)，\(0 \leq u, v < n\)，\(0 \leq k \leq 10^4\)，\(\max\{precision()\ is\ 6\}\). ## 输出格式
输出一行一个实数代表答案，结果保留一位小数。
样例 #1
样例输入 #1
1 | 4 |
样例输出 #1
1 | 12.0 |