记录编号	87237	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]奥运物流	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.390 s
提交时间	2014-02-03 08:34:34	内存使用	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};
double powK[SIZEN]={1};
int X;//当前接到1上的环上的点
void DP(int u,int maxd){//对结点u,计算所有离根不超过maxd的f值
	for(int i=0;i<son[u].size();i++) if(son[u][i]!=X&&son[u][i]!=1) DP(son[u][i],maxd+1);
	for(int d=1;d<=maxd;d++){
		int nowchange;
		if(maxd>1&&d==1) nowchange=1;//耗费了一次修改机会来把当前点挂在根上
		else nowchange=0;//当前的点没有修改,而是当前点的某个祖先修改了,此时u并不耗费修改机会
		double F[SIZEN]={0};
		for(int i=0;i<son[u].size();i++){
			int v=son[u][i];
			if(v==X||v==1) continue;//1到其父亲的边无效,X到其父亲的边无效(因为X的父亲已经改成了1)
			for(int j=M;j>=0;j--){//一个v只能更新一次,诸如"v改两次"和"v改三次"不能作为不同的物品
				for(int k=j;k>=0;k--) F[j]=max(F[j],F[k]+g[v][j-k][d]);//背包
			}
		}
		for(int i=nowchange;i<=M;i++) f[u][i][d]=F[i-nowchange]+C[u]*powK[d];//加上自己带来的可靠度
	}
	for(int j=0;j<=M;j++){//方便后面计算
		for(int d=0;d<maxd;d++)	g[u][j][d]=max(f[u][j][d+1],f[u][j][1]);
	}
}
void work(void){
	int len=2;
	double ans=0;
	for(X=father[1];X!=1;X=father[X],len++){//枚举从环上接到1的点
		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]);//背包
			}
		}
		int leftchange;
		if(father[X]==1) leftchange=M;//如果X的父亲是1,那么不必修改X
		else leftchange=M-1;//否则,X用掉了一次修改机会
		for(int i=0;i<=leftchange;i++) ans=max(ans,(F[i]+C[1])/(1-powK[len]));
		/*
		这里认为环长是len.即使DP的决策中将某个环上的点挂到了1从而导致环长不是len
		(一定小于len),也不会影响结果,因为环长长时1-K^len较大,结果显然没有枚举到
		将那个点直接挂在1上时优
		*/
	}
	printf("%.2lf",ans);
}
void read(void){
	scanf("%d%d%lf",&N,&M,&K);
	for(int i=1;i<=N;i++) powK[i]=powK[i-1]*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;
}