Maximizing Logistics System Reliability

The 2008 Beijing Olympics inspires a logistical challenge. The logistics system is composed of n logistic bases numbered from 1 to n. Each base i has exactly one successor S[i] (with S[i] ≠ i); however, a base may have several predecessors. Base 1 is the control base and from any base the goods can be eventually transported to base 1. Note that even the control base has a successor to allow circulation when needed.

For each base i, its reliability R(i) is defined recursively by

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

where the bases \(P_1, P_2, \dots, P_w\) are those with i as their successor (i.e., for which \(S_j = i\)). The constants \(C_i\) and \(k\) are positive real numbers with \(k<1\). The overall system reliability is positively correlated with R(1), the reliability of the control base.

You are allowed to modify the successor of at most m bases, except that the successor of the control base (base 1) cannot be modified. A modification consists in setting the successor of a base to 1. After modifications, it is still guaranteed that goods from any base can reach the control base. In the new configuration the reliability is computed in the same way but note that if a base i is attached directly to base 1 then its new depth becomes 1. In fact, if in the original configuration a node i is at depth d(i) in the tree (with R(1) computed as

$$R(1)=\sum_{u\in T} k^{d(u)} C_u, \quad d(1)=0),$$

then modifying base i (i.e. reattaching it directly to base 1) will change the depth of i and all nodes in its subtree. In particular, if a base i is reattached the new contribution from the subtree rooted at i becomes $$F(i)=\sum_{u \in T_i} k^{(\text{dist}(i,u)+1)} C_u, $$

where \(T_i\) is the subtree of i and \(\text{dist}(i,u)\) is the distance from i to u. Hence the benefit of reattaching base i is

$$B(i)= F(i)-G(i)= (k - k^{d(i)})\,H(i),$$

with $$H(i)=\sum_{u \in T_i} k^{\text{dist}(i,u)} C_u$$

and

$$G(i)=k^{d(i)}\,H(i).

Your task is to choose at most m bases (excluding base 1) to reassign their successor to 1 so as to maximize R(1) in the modified system. Note that if a base is reattached, none of its descendants should be reattached (since their benefit would be computed relative to a reattached ancestor).

## inputFormat

The input consists of three lines:

• The first line contains three numbers: an integer n (the number of logistic bases), an integer m (the maximum number of modifications allowed), and a floating‐point number k (with 0<k<1).
• The second line contains n positive real numbers: C₁, C₂, …, C_n.
• The third line contains n integers: S₁, S₂, …, S_n, where for each base i, S[i] denotes its successor. (Note: the successor of base 1 cannot be modified.)

It is guaranteed that from any base goods can be transported to base 1 in the original configuration.

## outputFormat

Output a single floating‐point number: the maximum possible reliability R(1) attainable after at most m modifications. Answers within an absolute or relative error of 10^-6 will be accepted.

## sample

5 1 0.5
10 1 1 1 1
2 1 2 3 3

11.5

$$