Aly_

分析

​ 先考虑怎么算 $R(i)$。

​ 考虑一个简单情况：$n$ 个点组成一个环，$1,2,\cdots n$ 顺次连边。列方程组

$\{R(i)=C_i+k*R(i\%n+1)\qquad(i\in\{1,2,\cdots,n\})$

​ 手动消元，每一行对着最后一行消，解得

$R(1)=\frac{\sum_i(C_ik^{i-1})}{1-k^n}$

​ 另一种情况，如果 $n$ 个点组成了一棵内向树，易得

$R(1)=\sum_iC_ik^{depth(i)}$

​ 其中 $depth$ 表示深度，$depth(1)=0$。

​ 总和上面两点就能得到一般情况下

$R(1)=\frac{\sum_iC_ik^{dis(i\rightarrow 1)}}{1-k^L}$

​ $L$ 为环长。

求解

​ 既然一个点的贡献只与其到 $1$ 经过的边数有关，可以直接无视从 $1$ 出发的边，以 $1$ 为根建内向树。考虑修改后继节点的过程，容易发现最优情况一定是把它的后继节点直接修改成 $1$。先不考虑环的问题，假设我们选择了 $p_1,\cdots,p_m$ 作为 $1$ 的儿子，设对于点 $x$，

$S(x)=C_x+\sum_{fa_i=x}kS(i)$

​ 则待求 $R(1)$ 可表示为

$S(1)+k\sum_{p_i}(1-k^{dis(p_i\rightarrow up_i)})S(p_i)$

​ 其中 $up_i$ 表示 $p_i$ 祖先中深度最大的被选中的点，即，向上跳跳到的第一个被选中点（若没有则看做 $1$）。

​ 有一个树形 DP 的形式了。

​ 再考虑环。容易发现原来环上的点变为一条树上到根路径。把一些点父亲修改后，环长必然缩小，并且一定是原来路径的一条前缀（从下往上），末端的点为这条路径上深度最大的选中点。

​ 设 $DP[i][j][k][l]$ 表示：当前处理 $i$ 子树内答案，上面最近的被选中点到 $i$ 的距离为 $j$，子树内选了 $k$ 个，原来环对应路径上的点选的最大深度为 $l$。

​ 转移枚举 $i$ 选不选，从第二维 $j+1$ 或 $0$ 转移上来，第三维和卷积，第四维 max 卷积。

​ 加入一些优化后可过本题。因为树上背包的优化有时会降复杂度，所以本算法复杂度玄学。（不高于 $n^5$ 级别）

​ 细节很有点多...?

#include<bits/stdc++.h>
#define int long long
#define N 60
#define inf 999999999999
using namespace std;
int n,m,nxt[N+1],lp[N+1],fl[N+1],dpt[N+1],dpt1,mdpt,sz[N+1];
double K,dp[N+1][N+1][N+1][N+1],g[N+1][N+1],pk[N+1],s[N+1],c[N+1],ans,f1[N+1][N+1];
vector<int>ve[N+1];
void putin(){
	cin>>n>>m>>K;
	for(int i=1;i<=n;i++){
		cin>>nxt[i];
		if(i!=1)ve[nxt[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)cin>>c[i];
}
void ttree(int x,int ndpt){
	dpt[x]=ndpt,sz[x]=1;if(nxt[1]==x)dpt1=ndpt;mdpt=max(mdpt,ndpt);
	for(int i=0;i<ve[x].size();i++){
		int ni=ve[x][i];
		if(ni!=1)ttree(ni,ndpt+1),sz[x]+=sz[ni];
	}
}
void ycl(){
	int np=1;
	do{lp[np]=1,np=nxt[np];}while(np!=1);
	pk[0]=1;for(int i=1;i<=n;i++)pk[i]=pk[i-1]*K;
	for(int i=1;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)for(int l=0;l<=n;l++)dp[i][j][k][l]=-inf;
	for(int i=1;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j][0][0]=0;
	for(int k=0;k<=n;k++)for(int l=0;l<=n;l++)if(k+l)f1[k][l]=-inf;
}
void dfs0(int x,int ndpt){
	s[x]=c[x],dpt[x]=ndpt;if(nxt[1]==x)dpt1=ndpt;
	for(int i=0;i<ve[x].size();i++){
		int ni=ve[x][i];
		if(ni!=1)dfs0(ni,ndpt+1),s[x]+=s[ni]*K;
	}
	for(int i=0;i<ve[x].size();i++){
		int ni=ve[x][i];
		for(int j=0;j<=ndpt;j++){
			for(int k=0;k<=n;k++)for(int l=0;l<=n;l++)g[k][l]=dp[x][j][k][l],dp[x][j][k][l]=-inf;
			for(int k=sz[x];k>=0;k--){
				for(int l=mdpt;l>=0;l--){
					if(g[k][l]<0||(l<dpt[x]&&l))continue;
					for(int p=min(sz[x]-k,sz[ni]);p>=0;p--){
						for(int q=mdpt;q>=0;q--){
							if(q<dpt[ni]&&q)continue;
							dp[x][j][k+p][max(l,q)]=max(dp[x][j][k+p][max(l,q)],g[k][l]+dp[ni][j+1][p][q]);
							if(p>=1)dp[x][j][k+p][max(l,(lp[ni]?max(dpt[ni],q):q))]=max(dp[x][j][k+p][max(l,(lp[ni]?max(dpt[ni],q):q))],g[k][l]+dp[ni][0][p-1][q]+(1-pk[j+1])*s[ni]);
						}
					}
				}
			}
		}
	}
}
signed main(){
	putin();
	ttree(1,0);
	ycl();
	dfs0(1,0);
	for(int i=0;i<ve[1].size();i++){
		int ni=ve[1][i];
		for(int k=0;k<=n;k++)for(int l=0;l<=n;l++)g[k][l]=f1[k][l],f1[k][l]=-inf;
		for(int k=sz[1];k>=0;k--){
			for(int l=mdpt;l>=0;l--){
				for(int p=sz[1]-k;p>=0;p--){
					for(int q=mdpt;q>=0;q--){
						if(p>=1)f1[k+p][max(l,(lp[ni]?max(dpt[ni],q):q))]=max(f1[k+p][max(l,(lp[ni]?max(dpt[ni],q):q))],g[k][l]+dp[ni][0][p-1][q]+(1-K)*s[ni]);
					}
				}
			}
		}
	}
	for(int i=0;i<=m+ve[1].size();i++){
		for(int j=0;j<=dpt1;j++){
			ans=max(ans,(K*(s[1]+f1[i][j])+(1-K)*c[1])/(1-pk[dpt1-j+2]));
		}
	}
	printf("%.2f\n",ans);
	return 0;
}