3683. 圣诞树

单点时限: 1.0 sec

内存限制: 256 MB

QQ 小方以前不会装饰圣诞树,现在他会了,所以他急切的想教会你。

QQ 小方会装饰这棵树上的一些结点,而圣诞树上的某些结点有装饰度(没有装饰度的结点的装饰度为 )。圣诞树是一棵有根树,且他的根结点编号为

QQ 小方会在圣诞树的结点中选出一些,挂上彩灯并点亮它们。

当一个结点被点亮时,以它为根的子树也会被照亮,但是它的祖先结点不会被照亮。每一个结点提供的美观度是其亮度乘上其装饰度,亮度被定义为其与其最近的被点亮的祖先的距离加 的倒数,即 (可以是它自己,此时亮度为 )。显然,如果一个结点没有被照亮或者点亮,那么这个结点不存在美观度。

单单讲给你听肯定是不够的,为了表现自己,QQ 小方现在要考考你。

QQ 小方现在定义整棵树的美观度为所有结点的美观度之和。他希望你在装饰圣诞树的同时,使得被装饰的这颗树的美观度达到最大。他想知道最大的美观度是多少。

简单题意:找一个至多 个点的集合 ,使得 最大。 定义为其与其最近的在集合 中的祖先的距离加 的倒数,即 (可以是它自己,此时亮度为 ),如果不存在这样的祖先,

输入格式

第一行一个整数 ()。

第二行 个整数,第 个整数 () 代表第 个结点的父结点的编号。

第三行两个以空格隔开的整数 (),分别代表有装饰的结点的数量,以及彩灯的数量。

接下来 行,每行两个以空格隔开的整数 (),分别代表有装饰的结点的编号及其装饰度。输入保证 () 。

输出格式

一行一个浮点数,代表这棵树的最大美观度。

绝对误差不超过 的答案都被认为是正确的。

样例

Input
3
1 1
3 1
1 1
2 2
3 3
Output
3.5000000000

提示

根结点不一定会被点亮,也就是可能会有被装饰的结点没有被点亮。

对于第一组样例,最佳方案是点亮 ,此时 的美观度是 的美观度是 的美观度是 ,共计

1 人解决,17 人已尝试。

1 份提交通过,共有 38 份提交。

9.9 EMB 奖励。

创建: 5 月前.

修改: 5 月前.

最后提交: 1 月,2 周前.

来源: N/A

题目标签