在 OI 界,有一位无人不知无人不晓,OI 水平前无古人后无来者的胡策,江湖人称一眼秒题胡大爷。
胡策最近从一名自称是小 O 的神秘男子那里收到了一棵神奇的小树苗。
这是一棵
这棵有根树上每个点都有一个权值,点
胡策大爷十分喜欢猴子,他打算在这棵树上养
因为根节点没有父亲,所以
在第
为了让猴子们的幸福指数的期望更大,胡策又从那名自称是小 O 的神秘男子那里买来了一袋叫“金坷垃”的肥料。如果给这棵有根树掺
请你告诉胡策,他该掺多少克的金坷垃,才能使猴子们幸福指数的期望最大呢?
输入格式
第一行一个正整数
第二行
第三行
输出格式
一行一个实数,表示掺适量的金坷垃时的最大幸福指数期望。
你的答案被认为是正确的当且仅当你的答案与标准答案的绝对误差或相对误差不超过
样例一
input
3 0 1 1 0 1 2
output
0.266666667
样例二
见样例数据下载。
限制与约定
对于 10% 的数据:
对于 20% 的数据:
对于 30% 的数据:
对于 50% 的数据:
对于 70% 的数据:
对于 100% 的数据:
数据保证有一定梯度。
数据都是随机生成的。即:节点
时间限制:
空间限制:
来源
中国国家集训队互测2015 - By 陈胤伯