Description

{{Alice designed a tree with $N$ nodes (including the root), numbered consecutively from $1$ to $N$, connected by $N - 1$ edges. Later, Bob added $K$ new edges that did not exist before (i.e., they are neither self-loops nor parallel edges), and called the resulting graph a "$K$-grafted tree".

Now Alice wants to color every node of the grafted tree using exactly $N$ available colors, numbered $1$ to $N$. Adjacent nodes must be colored differently. Suppose the number of nodes colored with color $i$ is $t_i$. Bob gives the following score:

$$\mathit{score}=\dfrac{t_1+\dfrac{1}{2}t_2+\dfrac{1}{3}t_3+\cdots+\dfrac{1}{N}t_N}{1+P\times (t_1+2t_2+3t_3+\cdots+Nt_N)}$$

Here $P$ is a non-negative coefficient. Alice wants to find a coloring that maximizes Bob’s score. Can you help her?}}

Input Format

{{The first line contains $2$ integers $N$ and $K$, as described. Lines $2$ through $N+K$ each contain two integers $u$ and $v$, giving the $N+K-1$ edges. First, the $N - 1$ tree edges are given, then the newly added edges. There are no self-loops or parallel edges. The last line contains a non-negative floating-point number $P$.

$K \le 2$, $1 \le N \le 2 \times 10^5$, $0 \le P < 10$.}}

Output Format

{{Output the maximum possible score, rounded to three decimal places.}}

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

0.253

Hint

{{2024-10-11 update: Updated the testdata precision issue.}}

Translated by ChatGPT 5