/ Vijos / 题库 /

嫁接树

嫁接树

描述

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

现在Alice希望对嫁接树的每一个结点进行染色,允许使用的颜色恰有N种,分别编号为1到N。Alice要求相邻两个结点要涂上不同的颜色。

假设颜色为i的结点有\(t_i\)个,则Bob给出了如下的评价分数:

\(score~=~\frac{t_1+\frac{t_2}{2}+\frac{t_3}{3}+\cdots +\frac{t_N}{N}}{1+P(t_1+2t_2+3t_3+\cdots +Nt_N)}\)

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

格式

输入格式

第一行有2个整数,依次为N和K,如题所述。

第二行到第N+K行,每行有两个整数u和v,依次给出了N+K-1条边。保证不存在自环,也不存在重边。

最后一行给定非负浮点数P。

输出格式

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

样例1

样例输入1

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

样例输出1

0.253

限制

对于50%的数据,K=0,\(1\le N\le 100000\),\(0\le P<10\)。其中有25%的数据P=0。

对于另外50%的数据,\(K\le 2\),\(1\le N\le 20000\),\(0\le P<10\)。其中也有25%的数据P=0。

来源

SDOI2015 round2 day2

信息

ID
1962
难度
9
分类
(无)
标签
递交数
97
已通过
1
通过率
1%
上传者

相关

在下列训练计划中:

RP++分类题库