Description

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

物流系统由若干物流基站组成, 以 \(1 \ldots n\) 进行编号. 每个物流基站 \(i\) 都有且仅有一个后继基站 \(S_i\), 而可以有多个前驱基站. 基站 \(i\) 中需要继续运输的物资都将被运往后继基站 \(S_i\), 显然一个物流基站的后继基站不能是其本身. 编号为 \(1\) 的物流基站称为控制基站, 从任何物流基站都可将物资运往控制基站. 注意控制基站也有后继基站, 以便在需要时进行物资的流通. 在物流系统中, 高可靠性与低成本是主要设计目. 对于基站 \(i\), 我们定义其 “可靠性”\(R(i)\) 如下:

设物流基站 \(i\) 有 \(w\) 个前驱基站 \(P_1, P_2, \ldots, P_w\), 即这些基站以 \(i\) 为后继基站, 则基站 \(i\) 的可靠性 \(R(i)\) 满足下式:

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

其中 \(C_i\) 和 \(k\) 都是常实数且恒为正, 且有 \(k\) 小于 \(1\).

整个系统的可靠性与控制基站的可靠性正相关, 我们的目标是通过修改物流系统, 即更改某些基站的后继基站, 使得控制基站的可靠性 \(R(1)\) 尽量大. 但由于经费限制, 最多只能修改 \(m\) 个基站的后继基站, 并且, 控制基站的后继基站不可被修改. 因而我们所面临的问题就是, 如何修改不超过 \(m\) 个基站的后继, 使得控制基站的可靠性 \(R(1)\) 最大化.

Input

输入第一行包含两个整数与一个实数,\(n, m, k\). 其中 \(n\) 表示基站数目,\(m\) 表示最多可修改的后继基站数目,\(k\) 分别为可靠性定义中的常数.

第二行包含 \(n\) 个整数, 分别是 \(S_1, S_2, \ldots, S_n\), 即每一个基站的后继基站编号.

第三行包含 \(n\) 个正实数, 分别是 \(C_1, C_2, \ldots, C_n\), 为可靠性定义中的常数.

Output

输出仅包含一个实数, 为可得到的最大 \(R(1)\). 精确到小数点两位.

Sample Input

4 1 0.5
2 3 1 3
10.0 10.0 10.0 10.0

Sample Output

30.00

Data Range

对于所有的数据, 满足 \(m \leq n \leq 60, C_i \leq 10^6, 0.3 \leq k \lt 1\), 请使用双精度实数, 无需考虑由此带来的误差.

Explanation

考虑一个环上距离节点 \(1\) 距离为 \(dep\) 对答案所做的贡献, 假设环的长度为 \(l\), 则贡献为 \(C_i \cdot k^{dep} \cdot (1 + k^{l} + k^{2l} + \ldots)\), 然后就是一个等比数列求和.

所以每个点 (环上的) 对答案的贡献为 \(\frac{c_1 \cdot k^{dep}}{1 - k^{l}}\), 于是我们尽可能的将 \(dep\) 减小, 这样收益最大.

用 \(f[i][j][k]\) 表示节点 \(i\) 为根的子树, 深度为 \(j\), 修改 \(k\) 次获得最大值, 然后树形 dp 即可.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define maximize(__x,__y) __x=max(__x,__y);
using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 64;
const llf infinit = 1e10;

int par[maxn];
void set_child(int u, int v)
{
    par[v] = u;
    return ;
}

int n, m;
llf K[maxn], c[maxn];
llf f[maxn][maxn][maxn], g[maxn][maxn][maxn],
    ff[maxn];

void dfs(int p, int depth)
{
    for (int v = 2; v <= n; v++) if (par[v] == p)
        dfs(v, depth + 1);
    for (int i = min(2, depth); i <= depth; i++) {
        memset(ff, 0, sizeof(ff));
        for (int v = 2; v <= n; v++) if (par[v] == p)
            for (int j = m; j >= 0; j--)
                for (int k = j; k >= 0; k--)
                    maximize(ff[j], ff[k] + g[v][j-k][i]);
        for (int j = 0; j <= m; j++)
            f[p][j][i] = ff[j] + c[p] * K[i];
    }
    if (depth > 1) {
        memset(ff, 0, sizeof(ff));
        for (int v = 2; v <= n; v++) if (par[v] == p)
            for (int j = m; j >= 0; j--)
                for (int k = j; k >= 0; k--)
                    maximize(ff[j], ff[k] + g[v][j-k][1]);
        for (int j = 1; j <= m; j++)
            f[p][j][1] = ff[j-1] + c[p] * K[1];
    }
    for (int i = 0; i <= m; i++)
        for (int j = 0; j < depth; j++)
            g[p][i][j] = max(f[p][i][j+1], f[p][i][1]);
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d%d%lf", &n, &m, &K[1]);
    for (int i = 2; i <= n; i++)
        K[i] = K[i-1] * K[1];
    for (int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        set_child(a, i);
    }
    for (int i = 1; i <= n; i++)
        scanf("%lf", &c[i]);
    // Results, globally and temporarily
    llf best_res = 0, res;
    for (int p = par[1], len = 2; p != 1; p = par[p], len++) {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        int buffer = par[p];
        par[p] = 1;
        for (int v = 2; v <= n; v++) if (par[v] == 1)
            dfs(v, 1);
        memset(ff, 0, sizeof(ff));
        for (int v = 2; v <= n; v++) if (par[v] == 1)
            for (int j = m; j >= 0; j--)
                for (int k = j; k >= 0; k--)
                    maximize(ff[j], ff[k] + f[v][j-k][1]);
        res = 0;
        for (int i = 0; i < m; i++)
            maximize(res, ff[i]);
        if (buffer == 1)
            res = max(res, ff[m]);
        maximize(best_res, (res + c[1]) / (1 - K[len]));
        par[p] = buffer;
    }
    // Output
    printf("%.2lf\n", best_res);
    return 0;
}