3683. 圣诞树

单点时限: 1.0 sec

内存限制: 256 MB

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

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

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

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

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

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

简单题意:找一个至多 $p$ 个点的集合 $S$ ,使得 $\sum _{i=1}^{n} (val_i\times dis_i)$ 最大。 $dis_i$ 定义为其与其最近的在集合 $S$ 中的祖先的距离加 $1$ 的倒数,即 $dis_i=\frac{1}{distance+1}$ (可以是它自己,此时亮度为 $1$),如果不存在这样的祖先, $dis_i=0$ 。

输入格式

第一行一个整数 $n$ ($3 \le n \le 100$)。

第二行 $n-1$ 个整数,第 $i$ 个整数 $a_i$ ($1 \le a_i \le i$) 代表第 $i+1$ 个结点的父结点的编号。

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

接下来 $p$ 行,每行两个以空格隔开的整数 $id_i,val_i$ ($1 \le id_i \le n,1 \le val_i \le 1000$),分别代表有装饰的结点的编号及其装饰度。输入保证 $id_i \neq id_j$ ($i \neq j$) 。

输出格式

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

绝对误差不超过 $10^{-4}$ 的答案都被认为是正确的。

样例

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

提示

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

对于第一组样例,最佳方案是点亮 $1$,此时 $1$ 的美观度是 $1 \times 1$, $2$ 的美观度是 $2 \times \frac{1}{2}$, $3$ 的美观度是 $3 \times \frac{1}{2}$,共计 $1+1+1.5=3.5$。

1 人解决,17 人已尝试。

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

9.9 EMB 奖励。

创建: 1 年,3 月前.

修改: 1 年,3 月前.

最后提交: 1 年前.

来源: N/A

题目标签