题目大意
题目分析
首先，对于以$i$为根的树，通过方程的迭代，发现$R(i)$等于$\sum_xC_xk^{d(x,i)}$，其中$d(x,i)$表示$x$与$i$间的距离。
考虑一个三元环：
带入消元可得$R(1)=\frac{C_1+kC_2+k^2C_3}{1-k^3}$。
因此可得，$R(1)=\frac{\sum_xC_xk^{d(x,1)}}{1-k^{len}}$，其中$len$是环长。
因此，每个点$x$对$1$的贡献为$C_xk^{d(x,i)}k^{d(i,1)}=C_xk^{d(x,1)}$。
因此，我们不需将环和树分开考虑，忽略$1$的出边，直接考虑$1$的所有子树信息。
枚举环长$len$，显然$len$不可能增加，因此分母一定，我们只需要将分子最大化即可。
故我们需要最大化$\sum_{i=1}^nC_ik^{d(i,1)}$。
显然对于每次修改，一定直接将$x$的后继设置为$1$。
设$f[i,j]$表示在点$i$的子树中分配$j$次修改所得到的最大贡献和。
考虑到若在$x$点更新$x$点所有儿子的代价，也就是考虑儿子对自己的影响（原理类似后序遍历），那么分为两种情况：
- 不修改$i$的后继，将$j$次修改分配到$i$子树中，再加上当前对$1$的贡献$C_ik^{d(i,1)}$。
- 若修改$i$的后继，假设$d(i,1)=tmp$，那么子树的所有贡献值需要除以$k^{tmp-1}$，但若儿子也修改过，就不能修改其贡献值。
转移过程似乎有了后效性？
考虑思考对未来的影响从而消除后效性。
不妨将每次祖先的决策放在后代考虑，即祖先对儿子的决策造成影响（原理类似先序遍历，当然实现形式还是后序遍历，此题若写成记忆化搜索将会非常的爽）。
设$f[i,j,d]$表示在$i$的子树中分配$j$次修改，且$i$到$1$的距离为$d$的最大贡献和。
因为已经知道祖先到$1$的距离，因此可以在儿子处计算出贡献。
令$g[i,j,d]=\max\lbrace f[i,j,d+1],f[i,j,1]\rbrace$，因此我们可以转移状态：
若不修改$i$的后继：$f[i,j,d]=\max\lbrace {\sum_{son}g[son,t,d]}\rbrace+C_ik^d$。
若修改$i$的后继：$f[i,j,1]=\max\lbrace {\sum_{son}g[son,t,1]}\rbrace+C_ik$。
这两个转移可以用背包完成。
最后我们得出$1$的所有儿子的状态，再用一次背包转移即可得出分子的最大值，除以枚举的分母即可统计答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=65;
int n,m,suc[maxn];
double k,ans=0,c[maxn],f[maxn][maxn][maxn],g[maxn][maxn][maxn],h[maxn],Pow[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void TreeDp(int Now,int depth) {
for(int Next=2; Next<=n; Next++)
if(suc[Next]==Now)
TreeDp(Next,depth+1);
for(int d=min(2,depth); d<=depth; d++) {
memset(h,0,sizeof(h));
for(int Next=2; Next<=n; Next++)
if(suc[Next]==Now)
for(int j=m; j>=0; j--)
for(int k=j; k>=0; k--)
h[j]=max(h[j],h[k]+g[Next][j-k][d]);
for(int i=0; i<=m; i++)
f[Now][i][d]=h[i]+c[Now]*Pow[d];
}
if(depth>1) {
memset(h,0,sizeof(h));
for(int Next=2; Next<=n; Next++)
if(suc[Next]==Now)
for(int j=m; j>=0; j--)
for(int k=j; k>=0; k--)
h[j]=max(h[j],h[k]+g[Next][j-k][1]);
for(int i=1; i<=m; i++)f[Now][i][1]=h[i-1]+c[Now]*k;
}
for(int i=0; i<=m; i++)
for(int d=0; d<depth; d++)
g[Now][i][d]=max(f[Now][i][d+1],f[Now][i][1]);
}
int main() {
n=Get_Int();
m=Get_Int();
scanf("%lf",&k);
for(int i=1; i<=n; i++)suc[i]=Get_Int();
for(int i=1; i<=n; i++)scanf("%lf",&c[i]);
Pow[0]=1;
for(int i=1; i<=n; i++)Pow[i]=Pow[i-1]*k;
for(int now=suc[1],len=2; now!=1; now=suc[now],len++) {
int tmp=suc[now];
suc[now]=1;
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int root=1; root<=n; root++)
if(suc[root]==1)TreeDp(root,1);
memset(h,0,sizeof(h));
for(int root=1; root<=n; root++)
if(suc[root]==1)
for(int j=m; j>=0; j--)
for(int k=j; k>=0; k--)
h[j]=max(h[j],h[k]+f[root][j-k][1]);
double Max=0;
for(int i=0; i<m; i++)Max=max(Max,h[i]);
if(tmp==1)Max=max(Max,h[m]);
ans=max(ans,(Max+c[1])/(1.0-Pow[len]));
suc[now]=tmp;
}
printf("%0.2lf",ans);
return 0;
}
|
