Description

A city is often divided into several zones, such as residential, commercial, and industrial.

City B is divided into two zones—the city center and the suburbs. Between these two zones lies a ring road encircling City B; the area inside the ring is the city center.

The whole city can be modeled as a connected unicyclic graph with $n$ vertices and $n$ edges. The unique cycle is the ring road. For any two vertices on the cycle, there are exactly $2$ simple paths between them. All other parts of the graph belong to the suburbs.

Jim wants to open shops in City B. However, the two endpoints of any edge cannot both have shops. Each vertex $i$ has a foot traffic $p_i$, and opening a shop at that vertex yields a profit of $p_i \times k$, where $k$ is a constant.

Find the maximum total profit Jim can earn.

Input Format

• The first line contains an integer $n$, the number of vertices in the city. The $n$ vertices are numbered $0 \sim n-1$.
• The second line contains $n$ integers. The $(i + 1)$-th integer is $p_i$, the foot traffic of vertex $i$.
• The next $n$ lines each contain two integers $u, v$, indicating that there is a road between $u$ and $v$.
• The last line contains a real number, the constant $k$.

Output Format

Output one line containing a real number representing the answer, rounded to one decimal place.

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

12.0

Hint

Constraints

• For $20\%$ of the testdata, $n \leq 100$.
• For another $20\%$ of the testdata, the number of vertices on the cycle does not exceed $2000$.
• For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq p_i \leq 10^4$, $0 \leq u, v < n$, $0 \leq k \leq 10^4$, and $k$ has at most $6$ digits after the decimal point.

Translated by ChatGPT 5