解题思路
评分是 ∑(M+1−dfn[i])ci，所以先算出每个点的期望 DFS 序，再枚举「改哪一个点」。
- 根的序恒为 1。若 u 只有一个孩子 v，则 E[dfn[v]]=E[dfn[u]]+1。若有两个孩子 a,b，先走 b 的概率是 cb/(ca+cb)，于是 E[dfn[a]]=E[dfn[u]]+1+ca+cbcb⋅sz[b]，b 对称。
- 不改任何点时，期望评分 B 可 O(M) 算出。
- 把 x 的货量改成 H：自身贡献变成 H⋅(M+1−E[dfn[x]])。仅当 x 有兄弟 s 时，改 cx 才会改写 x 与 s 两棵子树内部所有点的期望序，变化量分别是常数 Δx,Δs，对评分的影响也是 O(1) 可算。
- 根或独子改权值不改变任何概率。枚举每个 x 取最大，并与 B 比较。
题目内容
分拣中心把货位连成一棵有 M 个结点的二叉树，根结点编号为 0，每个结点至多两个孩子。第 i 个货位上放着货量 ci。巡检员按深度优先顺序走完整棵树：走到结点 u 时先记录 u，再进入其子树。若 u 恰有两个孩子 l 与 r，则先走进 l 的概率为
cl+crcl,
先走进 r 的概率为 cr/(cl+cr)；若只有一个孩子，则必定走进该孩子。
记 dfn[i] 为结点 i 被记录的顺序（从 1 开始）。整趟巡检的评分为
S=i=0∑M−1(M−dfn[i]+1)ci.
调度台可以把至多一个货位的货量改成目标值 H，也可以不改。求改完后评分期望的最大值。
输入描述
第一行一个整数 M（1≤M≤100000），表示结点数。
第二行 M−1 个整数，第 i 个数是结点 i 的父亲 pi（pi<i）。数据保证这是一棵二叉树。当 M=1 时这一行为空。
第三行 M 个整数 c0,c1,…,cM−1（1≤ci≤103），表示各货位货量。
第四行一个整数 H（1≤H≤103），表示可改成的目标货量。
输出描述
输出一个实数，表示最大期望评分。绝对误差或相对误差不超过 0.0001 即视为正确。
样例1
输入
3
0 0
2 3 4
10
输出
40.5714
说明
根 0 的两个孩子是 1 和 2。把结点 0 的货量改成 10 时，遍历概率不变，期望评分为 40.5714，优于改其他点或不改。
样例2
输入
2
0
8 1
3
输出
19.0000
说明
链上只有一个孩子，改权值不影响顺序。不改时期望为 17；把结点 0 改成 3 反而变差，把结点 1 改成 3 得到 19。
样例3
输入
4
0 1 2
1 2 3 4
5
输出
36.0000
说明
这是一条链。越早被记录的点系数越大，把根的货量改成 5 最优，期望为 36。
数据范围
- 1≤M≤100000
- 1≤ci,H≤103
- 父亲满足 pi<i，且每个点至多两个孩子
- 所有输入均为整数
