记录编号	69558	评测结果	AAAAAAAAAA
题目名称	289.[NOI 2008]奥运物流	最终得分	100
用户昵称	GDFRWMY	是否通过	通过
代码语言	Pascal	运行时间	0.451 s
提交时间	2013-09-18 13:01:17	内存使用	15.69 MiB

    var
     tu1,tu2:array[1..1000,1..1000] of longint;
jie:array[0..1000] of double;
    tag:array[1..1000] of boolean;

    b,p,father,dis,son,bro,temp:array[1..1000] of longint;
    f:array[0..100,0..100,0..100] of double;
    c:array[1..60] of double;
    i,j,k,n,m,pn,x,y,l,mm:longint;
    ans,d,count:double;


    function max(x,y:double):double;
    begin
    if x>y then max:=x else max:=y;
    end;



    procedure dfs(x:longint);
    var i:longint;
    begin
    tag[x]:=true;

    for i:=1 to n do
    if (tu2[x,i]=1)and(tag[i]=false) then
    begin
    if son[x]=0 then
    begin
    son[x]:=i;
    temp[x]:=0;
    end;
    if temp[x]>0 then
    bro[temp[x]]:=i;
    dfs(i);
    temp[x]:=i;
    end;
    end;

    function tree(i,j,k:longint):double;
    var
    r:longint;
    z:double;
    begin
    if f[i,j,k]=0 then
    begin
    if i>0 then
    begin
    if (tu2[1,i]=0)and(j>0) then
    begin
    for r:=0 to j-1 do
    f[i,j,k]:=max(f[i,j,k],tree(son[i],r,1)+tree(bro[i],j-1-r,k));
    f[i,j,k]:=f[i,j,k]+c[i]*jie[1];
    end;
    z:=c[i]*jie[k+dis[i]];
    for r:=0 to j do
    f[i,j,k]:=max(f[i,j,k],tree(son[i],r,k+dis[i])+tree(bro[i],j-r,k)+z);
    end;
    end;
    tree:=f[i,j,k];

    end;








    begin
    assign(input,'trans.in');
    assign(output,'trans.out');
    reset(input);
    rewrite(output);
    readln(n,m,d);
    for i:=1 to n do read(father[i]);
    for i:=1 to n do read(c[i]);
    count:=0;
    for i:=2 to n do count:=count+c[i];

    for i:=1 to n do
    begin
    tu1[i,father[i]]:=1;
    tu1[father[i],i]:=1;
    end;
    k:=father[1];
    while k<>1 do
    begin
    inc(pn);
    p[pn]:=k;
    k:=father[k];
    end;
    jie[0]:=1;
    for i:=1 to n do
    jie[i]:=jie[i-1]*d;

    for i:=1 to pn do
    begin
    if (count*d+c[1])/(1-jie[i+1])<ans then break;
    if father[p[i]]<>1 then k:=1 else k:=0;
    if m>=k then
    begin
    mm:=m-k;
    tu2:=tu1;
        for j:=1 to n do dis[j]:=1;
    k:=0;
    for j:=i downto 1 do
    begin
    inc(k);
    dis[p[j]]:=k;
    tu2[p[j],father[p[j]]]:=0;
    tu2[father[p[j]],p[j]]:=0;
    tu2[p[j],1]:=1;
    tu2[1,p[j]]:=1;
    end;
    fillchar(son,sizeof(son),0);
    fillchar(bro,sizeof(bro),0);
    fillchar(tag,sizeof(tag),0);
    fillchar(f,sizeof(f),0);


    dfs(1);




    ans:=max(ans,(tree(son[1],mm,0)+c[1])/(1-jie[i+1]));

    end;
    end;
    writeln(ans:0:2);
    close(input);
    close(output);
    end.