儿童节快乐~ 尽管从某种程度上我早就不是那个能过六一节的儿童了
# 题面
> 洛谷 P4438
# 解析
题目中非常重要的提示是“树深不超过40”（可惜我以为这是限制答案不超过long long……不过讲道理限制树深确实非常特殊，应该有特别意义）
因为代价的计算式中出现了 $x,y$ 的乘积项，并不方便处理，这就意味着 DP 状态中一定要储存 $x,y$ 的相关信息。对于一般的树形DP，我们往往会储存一个子树的信息，但是这道题我们可以储存当前点到根的路径上的信息：
定义 f[u][x][y] 表示 $u$ 到 $1$ 的路径上有 $x$ 条未翻新的公路、$y$ 条未翻新的铁路对应的最小子树代价和。
不难得到转移式：
$v_x$ 指 $u$ 通过公路连接的点，$v_y$ 指 $u$ 通过铁路连接的点。那么 $\min$ 中前者表示修复公路、后者表示修复铁路。
如果 $v$ 是乡村，则 $f[v][x][y]=(a_{v}+x)(b_v+y)c_v$。
然后从下往上DP即可，又因为出题人非常好心地让树的节点标号和树深相联系，甚至都不需要写DFS。
# 源代码
点击展开/折叠代码
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e4+3;
int n;
int lnk[N][2],val[N][3],fa[N<<1],cntx[N<<1],cnty[N<<1];
ll f[N][41][41];
#define F(u,x,y) ((u)>0? f[u][x][y]:1ll*val[-u][2]*(val[-u][0]+x)*(val[-u][1]+y))
inline int Ri(){
register int a=0,b=1,c=getchar();
while(c<'0' || '9'<c) b=(c=='-'? -1:b),c=getchar();
while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
return a*b;
}
int main(){
n=Ri();
for(int i=1;i<n;i++)
for(int j=0;j<2;j++){
lnk[i][j]=Ri();
if(lnk[i][j]>0) fa[lnk[i][j]]=i;
}
for(int i=1;i<=n;i++)
for(int j=0;j<3;j++)
val[i][j]=Ri();
memset(f,0x3f,sizeof f);
for(int u=2;u<n;u++){
cntx[u]=cntx[fa[u]]+(lnk[fa[u]][0]==u);
cnty[u]=cnty[fa[u]]+(lnk[fa[u]][1]==u);
}
for(int u=n-1;u>=1;u--){
int vx=lnk[u][0],vy=lnk[u][1];
for(int x=0;x<=cntx[u];x++)
for(int y=0;y<=cnty[u];y++){
f[u][x][y]=min(f[u][x][y],F(vx,x,y)+F(vy,x,y+1));
f[u][x][y]=min(f[u][x][y],F(vx,x+1,y)+F(vy,x,y));
}
}
printf("%lld\n",f[1][0][0]);
return 0;
}
|
THE END
Thanks for reading!