[NOI2008]奥运物流

$2008$ 年北京奥运会即将开幕，举国上下都在为这一盛事做好准备。为了高效、成功地举办奥运会，对物流系统进行合理规划是必不可少的。

物流系统由 $N$ 个物流基站组成，编号为 $1$ 到 $N$ 。每个物流基站 $i$ 都有且仅有一个后继基站 $S_i$ ，但可以有多个前驱基站。基站 $i$ 中需要继续运输的物资都将被运往其后继基站 $S_i$ 。一个物流基站的后继基站不能是其自身。

编号为 $1$ 的物流基站称为控制基站。从任意物流基站出发，物资都可以被运往控制基站。控制基站也有后继基站，以便在需要时进行物资流通。

在物流系统中，高可靠性与低成本是主要的设计目标。对于基站 $i$ ，定义其可靠性 $R(i)$ 如下：设基站 $i$ 有 $w$ 个前驱基站 $P_1,P_2,\ldots,P_w$ ，即这些基站均以 $i$ 为后继基站，则

R(i)=C_i+k\sum_{j=1}^{w}R(P_j)。

其中， $C_i$ 和 $k$ 均为恒正的实数，且 $k<1$ 。

整个系统的可靠性与控制基站的可靠性正相关。你可以修改某些基站的后继基站，使控制基站的可靠性 $R(1)$ 尽可能大。由于经费有限，最多只能修改 $m$ 个基站的后继基站，并且控制基站的后继基站不可修改。

请计算修改后能够得到的最大 $R(1)$ 。

输入格式

第一行包含两个整数 $N,m$ 和一个实数 $k$ ，分别表示物流基站的数量、最多可以修改后继基站的基站数量，以及可靠性定义中的常数。

第二行包含 $N$ 个整数 $S_1,S_2,\ldots,S_N$ ，其中 $S_i$ 表示基站 $i$ 的后继基站编号。

第三行包含 $N$ 个正实数 $C_1,C_2,\ldots,C_N$ ，表示可靠性定义中的常数。

输出一个实数，表示能够得到的最大 $R(1)$ ，保留小数点后两位。

4 1 0.5
2 3 1 3
10.0 10.0 10.0 10.0

30.00

本题为 NOI 2008 试题「奥运物流」，题面与测试数据整理自 BZOJ 1065。

4 1 0.5
2 3 1 3
10.0 10.0 10.0 10.0

30.00