嫁接树
测试数据来自 system/1962
描述
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
- 1894
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者