城市环路
题目描述
一座城市,往往会被人们划分为几个区域,例如住宅区、商业区、工业区等等。
B 市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕 B 市的环路,环路之内便是 B 市中心。
整个城市可以看做一个 $n$ 个点,$n$ 条边的单圈图(保证图连通),唯一的环便是绕城的环路。保证环上任意两点有且只有 $2$ 条简单路径互通。图中的其它部分皆隶属城市郊区。
现在,有一位名叫 Jim 的同学想在 B 市开店,但是任意一条边的 $2$ 个点不能同时开店,每个点都有一定的人流量,第 $i$ 个点的人流量是 $p_i$,在该点开店的利润就等于 $p_i×k$,其中 $k$ 是一个常数。
Jim 想尽量多的赚取利润,请问他应该在哪些地方开店?
输入输出格式
输入格式
第一行一个整数 $n$,代表城市中点的个数。城市中的 $n$ 个点由 $0 \sim n-1$ 编号。
第二行有 $n$ 个整数,第 $(i + 1)$ 个整数表示第 $i$ 个点的人流量 $p_i$。
接下来 $n$ 行,每行有两个整数 $u, v$,代表存在一条连接 $u$ 和 $v$ 的道路。
最后一行有一个实数,代表常数 $k$。
输出格式
输出一行一个实数代表答案,结果保留一位小数。
输入输出样例
输入样例 #1
4
1 2 1 5
0 1
0 2
1 2
1 3
2
输出样例 #1
12.0
说明
#### 数据规模与约定
- 对于 $20\%$ 的数据,保证 $n \leq 100$。
- 另有 $20\%$ 的数据,保证环上的点不超过 $2000$ 个。
- 对于 $100\%$ 的数据,保证 $1 \leq n \leq 10^5$,$1 \leq p_i \leq 10^4$,$0 \leq u, v < n$,$0 \leq k \leq 10^4$,$k$ 的小数点后最多有 $6$ 位数字。