T289898 「JEOI-R1」补给

出题 | 标程 | 数据 | 验题 | 题解 | | -----------: | -----------: | -----------: | -----------: | -----------: | | [_JF_](https://www.luogu.com.cn/user/361141) | [_JF_](https://www.luogu.com.cn/user/361141) | [tianhangj](https://www.luogu.com.cn/user/263063) | [SDqwq](https://www.luogu.com.cn/user/365542) | [_JF_](https://www.luogu.com.cn/user/361141) | 2337 年，各个军阀之间即将展开战争，[_JF_](https://www.luogu.com.cn/user/361141) 也被迫卷入，他开始积极的备战，但是一开始筹备期间，[_JF_](https://www.luogu.com.cn/user/361141) 就遇到了补给的问题。

已知 [_JF_](https://www.luogu.com.cn/user/361141) 有 $n$ 支军队，军队之间有 $n-1$ 对上下级关系。除 $1$ 号军队外，每支军队在这些上下级关系下的最上级都是 $1$ 号军队。 由于每支军队的实力不同，他们所需要的补给数量也各不一样。现在每支军队手里有 $a_i$ 单位的补给，而他们实际需要 $b_i$ 单位的补给。我们定义 **“盈余”** 为每支军队多出来的补给。 对于军队 $u$ 而言，他只可以向他的直接下级军队 $v$（节点的儿子）征收补给，但是征收的补给不可超过 $v$ 的盈余，并且上传的补给数量可以是浮点数。但是 JF 管理的地方非常混乱，$v$ 向 $u$ 运输补给的时候，总会有 $w\%$ 的补给在路途中被强盗打劫（暂称为打劫率）。 注意，不同的子节点 $v$ **可以选择**把当前层要集中的补给一起上传，假设 $2$ 号给 $1$ 号上传 $2$ 个单位补给，$3$ 号给 $1$ 号上传 $3$ 个补给，打劫率是 $50\%$。那么 $1$ 号可以得到 $(2+3)-(2+3) \times 50\%=2.5$ 个单位补给。 运送补给的费用是每单位花费 $k$，由于 JF 的疆域内有完整的铁路网络，补给只有在打包的时候需要花费，因此如果一个补给连续向上运输，不需要额外花费（即使中途有军队卸下补给仍然不需要额外花费）。 现在 JF 希望你帮助他求出：在保证每支军队的补给充足情况下最小的开支。 数据保证至少存在一种方式使得每支军队都可以得到补给。

第一行三个 $n,w,k$，如题所示。 第二行至第 $n$ 行共 $n-1$ 行，每行两个数 $u_i,v_i$ 表示 $u_i$ 是 $v_i$ 的上级。 第 $n+1$ 行 $n$ 个整数 $a_1,a_2,a_3,...,a_n$，表示每支军队的现有的补给。 第 $n+2$ 行 $n$ 个整数 $b_1,b_2,b_3,...,b_n$，表示每支军队的所需补给。

一行一个浮点数 $s$，表示最小开支。

**【样例解释 #1】** 首先 $4$ 号军队向 $2$ 号军队传送 $6$ 个单位的补给，这时候可以到达 $2$ 号是 $3$ 个单位补给，运费是 $6$。 由于 $2$ 号要 $1$ 个单位补给，拿完以后它向上传送 $2$ 个单位补给，这时候 $1$ 号可以获得 $1$ 个补给。 $3$ 向 $1$ 号上传 $2$ 个单位补给，$1$ 号可以收到 $1$ 点补给。这时候 $1$ 号就可以满足消耗了。运费是 $2$。 运费共计 $2+6=8$。 ------------ **【数据范围】** 对于 $30\%$ 的数据，有 $n \le 100$。 对于 $60\%$ 的数据，有 $n \le 10^4$。 对于另外 $10\%$的数据，保证树是一个菊花图。 对于另外 $10\%$ 的数据，有 $\forall{1\le i\le n}$，$a_i\ge b_i$。 对于 $100\%$ 的数据，有 $1\leq n \le 4\times 10^5$，$1\leq w\leq100$，$1\leq k\leq20$， $\forall 1 \le i \le n,0 \le a_i,b_i