P3319 {{[SDOI2015] Grafting Tree}}

{{}}

{{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?}}

{{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 the maximum possible score, rounded to three decimal places.}}

{{2024-10-11 update: Updated the testdata precision issue.}} Translated by ChatGPT 5