P4202 [NOI2008] Olympic Logistics

The 2008 Beijing Olympic Games are about to open, and the whole country is preparing for this grand event. To hold the Games efficiently and successfully, it is essential to plan the logistics system. The logistics system consists of several logistics base stations, numbered from $1$ to $n$. Each logistics base station $i$ has exactly one successor station $S_i$, and may have multiple predecessor stations. All goods at station $i$ that need to continue transportation will be sent to its successor station $S_i$. Obviously, a station cannot be its own successor. Station $1$ is called the control station, and goods can be sent from any station to the control station. Note that the control station also has a successor station, so that circulation is possible when needed. In the logistics system, high reliability and low cost are the main design goals. For station $i$, we define its “reliability” $R(i)$ as follows: Suppose station $i$ has $w$ predecessor stations $P_1, P_2, \cdots, P_w$, i.e., these stations take $i$ as their successor station, then the reliability $R(i)$ of station $i$ satisfies: $$R(i)=C_i+k \sum_{j=1}^{w}R(P_j).$$ Here $C_i$ and $k$ are fixed positive real numbers, and $k$ is less than $1$. The overall system reliability is positively correlated with the reliability of the control station. Our goal is to modify the logistics system—i.e., change the successors of some stations—so that the reliability $R(1)$ of the control station is as large as possible. Due to budget constraints, at most $m$ stations’ successors can be modified, and the successor of the control station cannot be modified. Therefore, the problem is: how to modify the successors of no more than $m$ stations to maximize the reliability $R(1)$ of the control station.

The first line contains two integers and a real number, $n, m, k$. Here $n$ is the number of stations, $m$ is the maximum number of successor changes allowed, and $k$ is the constant in the reliability definition. The second line contains $n$ integers, $S_1, S_2 \cdots S_n$, the successor station index of each station. The third line contains $n$ positive real numbers, $C_1, C_2 \cdots C_n$, the constants in the reliability definition.

Output a single real number: the maximum achievable $R(1)$. Round to two decimal places.

[Sample explanation] In the original logistics system (as shown in the left figure), the reliabilities of the $4$ stations are $22.8571, 21.4286, 25.7143, 10$ in order. The optimal plan is to change the successor of station $2$ to station $1$. Then the reliabilities of the $4$ stations become $30, 25, 15, 10$ in order. The testdata is distributed as follows: 测试数据编号| $n$ | $m$ :-:|:-:|:-: $1$|$\leq 6$|$\leq 6$ $2$|$\leq 12$|$\leq 12$ $3$|$\leq 60$|$0$ $4$|$\leq 60$|$1$ $5$|$\leq 60$|$n-2$ $6, 7, 8, 9, 10$|$\leq 60$|$\leq 60$ For all testdata, $m \leq n \leq 60$, $C_i \leq 10^6$, $0.3 \leq k < 1$. Please use double-precision floating-point numbers; you do not need to worry about the error introduced. Translated by ChatGPT 5