2 人解决，19 人已尝试。
2 份提交通过，共有 136 份提交。
9.9 EMB 奖励。
单点时限: 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}$ 的答案都被认为是正确的。
3 1 1 3 1 1 1 2 2 3 3
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$。
2 人解决，19 人已尝试。
2 份提交通过，共有 136 份提交。
9.9 EMB 奖励。
创建: 5 年前.
修改: 5 年前.
最后提交: 10 月前.
来源: N/A