http://www.lydsy.com/JudgeOnline/problem.php?id=1065
思路:由于n个点，有n条边，因此由根就会引出一个环，我们枚举环的长度，在那个长度断开，我们假设len为环的长度。
由于R(i)满足
而产生环时，R[1]=Σci*k^di + R[1]*(k^len),得到
R[1]=(Σci*k^di)/(1-k^len)
因此我们枚举len，然后做树形DP，f[i][j][k]代表第i个点，修改了j次，当前深度为k
那么最后的贡献是Σf[i][j][1]，i为1的直接儿子，用一个01背包统计，最后答案就是(ans+c[1])/(1-k^len)
有个蛋疼的地方就是做01背包的时候。。要注意循环变量的顺序，不要重复统计。。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
int n,m,pre[];
double K[],c[],f[][][],g[][][],F[];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void dp(int x,int dep){
for (int i=;i<=n;i++) if (pre[i]==x) dp(i,dep+);
for (int d=std::min(,dep);d<=dep;d++){
for (int j=;j<=m;j++) F[j]=;
for (int i=;i<=n;i++)
if (pre[i]==x)
for (int j=m;j>=;j--)
for (int k=j;k>=;k--)
F[j]=std::max(F[j],F[k]+g[i][j-k][d]);
for (int i=;i<=m;i++)
f[x][i][d]=F[i]+c[x]*K[d];
}
if (dep>){
for (int i=;i<=m;i++) F[i]=;
for (int i=;i<=n;i++)
if (pre[i]==x)
for (int j=m;j>=;j--)
for (int k=j;k>=;k--)
F[j]=std::max(F[j],F[k]+g[i][j-k][]);
for (int i=;i<=m;i++)
f[x][i][]=F[i-]+c[x]*K[];
}
for (int j=;j<=m;j++)
for (int d=;d<dep;d++)
g[x][j][d]=std::max(f[x][j][d+],f[x][j][]);
}
int main(){
n=read();m=read();scanf("%lf",&K[]);
for (int i=;i<=n;i++) K[i]=K[i-]*K[];
for (int i=;i<=n;i++) pre[i]=read();
for (int i=;i<=n;i++) scanf("%lf",&c[i]);
double ans=;
for (int I=pre[],len=;I-;I=pre[I],len++){
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
for (int k=;k<=n;k++)
f[i][j][k]=g[i][j][k]=;
int tmp=pre[I];pre[I]=;
for (int i=;i<=n;i++) if (pre[i]==) dp(i,);
for (int i=;i<=m;i++) F[i]=;
for (int i=;i<=n;i++)
if (pre[i]==)
for (int j=m;j>=;j--)
for (int k=j;k>=;k--)
F[j]=std::max(F[j],F[k]+f[i][j-k][]);
double now=;
for (int i=;i<m;i++) now=std::max(now,F[i]);
if (tmp==) now=std::max(now,F[m]);
pre[I]=tmp;
ans=std::max(ans,(now+c[])/(-K[len]));
}
printf("%.2lf\n",ans);
}