题目描述

Alice 设计了一个树结构，有 $N$ 个结点（包括根）被依次编号为 $1$ 到 $N$，由 $N-1$ 条边连接。后来，Bob 在上面增加了 $K$ 条原来没有的边（也就是说既不是自环，也不会因此产生重边）并称这样得到的图为” $K$-嫁接树“。

现在 Alice 希望对嫁接树的每一个结点进行染色，允许使用的颜色恰有 $N$ 种，分别编号为 $1$ 到 $N$。Alice 要求相邻两个结点要涂上不同的颜色。假设颜色为 $i$ 的结点有 $t_i$ 个，则 Bob 给出了如下的评价分数：

$$\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)} $$

其中 $P$ 为非负系数。现在，Alice 希望可以找到一种染色方案，使得 Bob 给出来的评分最大。你能帮助他吗？

输入格式

第一行有 $2$ 个整数，依次为 $N$ 和 $K$，如题所述。第二行到第 $N+K$ 行，每行有两个整数 $u$ 和 $v$，依次给出了 $N+K-1$ 条边。其中，首先给出 $N - 1$ 条树边，其次给出新增加的边。保证不存在自环，也不存在重边。最后一行给定非负浮点数 $P$。

$K \le 2$，$1 \le N \le 2 \times 10^5$，$0 \le P<10$。

输出格式

输出最大的可能评分，四舍五入保留到小数点后第三位。

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

0.253

提示

2024-10-11 update: 更新了数据精度问题