#P1453. 城市环路

    ID: 78 远端评测题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>动态规划,dp图论环套树,基环树

城市环路

题目背景

一座城市,往往会被人们划分为几个区域,例如住宅区、商业区、工业区等等。

B 市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕 B 市的环路,环路之内便是 B 市中心。

题目描述

整个城市可以看做一个 nn 个点,nn 条边的单圈图(保证图连通),唯一的环便是绕城的环路。保证环上任意两点有且只有 22 条简单路径互通。图中的其它部分皆隶属城市郊区。

现在,有一位名叫 Jim 的同学想在 B 市开店,但是任意一条边的 22 个点不能同时开店,每个点都有一定的人流量,第 ii 个点的人流量是 pip_i,在该点开店的利润就等于 pi×kp_i×k,其中 kk 是一个常数。

Jim 想尽量多的赚取利润,请问他应该在哪些地方开店?

输入格式

第一行一个整数 nn,代表城市中点的个数。城市中的 nn 个点由 0n10 \sim n-1 编号。

第二行有 nn 个整数,第 (i+1)(i + 1) 个整数表示第 ii 个点的人流量 pip_i

接下来 nn 行,每行有两个整数 u,vu, v,代表存在一条连接 uuvv 的道路。

最后一行有一个实数,代表常数 kk

输出格式

输出一行一个实数代表答案,结果保留一位小数。

4
1 2 1 5
0 1
0 2
1 2
1 3
2

12.0

提示

数据规模与约定

  • 对于 20%20\% 的数据,保证 n100n \leq 100
  • 另有 20%20\% 的数据,保证环上的点不超过 20002000 个。
  • 对于 100%100\% 的数据,保证 1n1051 \leq n \leq 10^51pi1041 \leq p_i \leq 10^40u,v<n0 \leq u, v < n0k1040 \leq k \leq 10^4kk 的小数点后最多有 66 位数字。