记录编号	87235	评测结果	AAAAAAAAAA
题目名称	289.[NOI 2008]奥运物流	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.495 s
提交时间	2014-02-02 22:48:12	内存使用	5.55 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN=70;
int N,M;
double K;
int father[SIZEN]={0};
vector<int> son[SIZEN];
double C[SIZEN]={0};
double f[SIZEN][SIZEN][SIZEN]={0};
double g[SIZEN][SIZEN][SIZEN]={0};
int X;//当前接到1上的环上的点
void DP(int u,int maxd){//对结点u,计算所有离根不超过maxd的f值
	//cout<<u<<" "<<maxd<<endl;
	for(int i=0;i<son[u].size();i++) if(son[u][i]!=X&&son[u][i]!=1) DP(son[u][i],maxd+1);
	//cout<<u<<" "<<maxd<<"as follow:"<<endl;
	for(int d=1;d<=maxd;d++){
		int nowchange;
		if(maxd>1&&d==1) nowchange=1;//耗费了一次修改机会来把当前点挂在根上
		else nowchange=0;
		double F[SIZEN]={0};
		for(int i=0;i<son[u].size();i++){
			int v=son[u][i];
			if(v==X||v==1) continue;
			//cout<<u<<" "<<maxd<<" "<<v<<"as follow:"<<endl;
			for(int j=M;j>=0;j--){//一个v只能更新一次,诸如"v改两次"和"v改三次"不能作为一个物品
				//for(int k=0;k<=M;k++){cout<<F[k]<<" ";}cout<<endl;
				for(int k=j;k>=0;k--){
					//cout<<v<<" "<<j-k<<" "<<d<<" "<<F[k]<<" "<<g[v][j-k][d]<<endl;
					//cout<<k<<" "<<j<<" "<<F[k]<<endl;
					F[j]=max(F[j],F[k]+g[v][j-k][d]);
					//cout<<j<<" "<<F[0]<<" "<<F[1]<<endl;
				}
				//for(int k=0;k<=M;k++){cout<<F[k]<<" ";}cout<<endl;cout<<endl;
			}
			/*for(int j=M;j>=0;j--){
				//for(int k=0;k<=M;k++){cout<<F[k]<<" ";}cout<<endl;
				for(int k=M;k>=j;k--){
					//cout<<v<<" "<<j<<" "<<d<<" "<<F[k-j]<<" "<<g[v][j][d]<<endl;
					//cout<<k-j<<" "<<F[k-j]<<endl;
					F[k]=max(F[k],F[k-j]+g[v][j][d]);
				}
				//for(int k=0;k<=M;k++){cout<<F[k]<<" ";}cout<<endl;cout<<endl;
			}*/
		}
		for(int i=nowchange;i<=M;i++){
			//cout<<u<<" "<<i<<" "<<d<<" "<<F[i-nowchange]<<" "<<C[u]*pow(K,d+0.0)<<endl;
			f[u][i][d]=F[i-nowchange]+C[u]*pow(K,d+0.0);
			//cout<<d<<" "<<pow(K,d+0.0)<<endl;
		}
		//for(int i=0;i<=M;i++) g[u][i][d]=max(f[u][i][d],f[u][i][1]);
		//for(int i=0;i<=M;i++) cout<<F[i]<<" ";cout<<endl;
	}
	for(int j=0;j<=M;j++){
		for(int d=0;d<maxd;d++){
			//cout<<u<<" "<<j<<" "<<d<<" "<<f[u][j][d+1]<<" "<<f[u][j][1]<<endl;
			g[u][j][d]=max(f[u][j][d+1],f[u][j][1]);
		}
	}
	//for(int i=0;i<=M;i++){for(int j=0;j<maxd;j++){cout<<g[u][i][j]<<" ";}cout<<endl;}
}
void work(void){
	int len=2;
	double ans=0;
	for(X=father[1];X!=1;X=father[X],len++){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		for(int i=2;i<=N;i++) if(father[i]==1||i==X) DP(i,1);
		double F[SIZEN]={0};
		for(int i=2;i<=N;i++){
			if(!(father[i]==1||i==X)) continue;
			for(int j=M;j>=0;j--){
				for(int k=j;k>=0;k--){
					F[j]=max(F[j],F[k]+f[i][j-k][1]);
				}
			}
			/*for(int j=0;j<=M;j++){
				for(int k=M;k>=j;k--) F[k]=max(F[k],F[k-j]+f[i][j][1]);
			}*/
		}
		int leftchange;
		if(father[X]==1) leftchange=M;
		else leftchange=M-1;
		for(int i=0;i<=leftchange;i++) ans=max(ans,(F[i]+C[1])/(1-pow(K,len+0.0)));
	}
	printf("%.2lf",ans);
}
void read(void){
	scanf("%d%d%lf",&N,&M,&K);
	for(int i=1;i<=N;i++){
		scanf("%d",&father[i]);
		son[father[i]].push_back(i);
	}
	for(int i=1;i<=N;i++) scanf("%lf",&C[i]);
}
int main(){
	freopen("trans.in","r",stdin);
	freopen("trans.out","w",stdout);
	read();
	work();
	return 0;
}