[洛谷 4438,loj 2510][HNOI/AHOI2018]道路

题目链接

https://www.luogu.com.cn/problem/P4438

https://loj.ac/problem/2510

题解

设 \(f_{i,j,k}\) 表示对于 \(i\) 节点所在子树，从根节点到 \(i\) 经过 \(j\) 条未翻修公路，\(k\) 条未翻修公路时，整棵子树最小代价。

分两种情况讨论：

对于叶节点，我们枚举 \(j,k\)，直接按题目中式子计算即可。

对于非叶子节点，我们枚举翻修铁路或公路，转移方程如下：

$$f_{i,j,k}=\min\{f_{ls,j+1,k}+f_{rs,j,k},f_{ls,j,k}+f_{rs,j,k+1}\}$$

#include <iostream>
#include <algorithm>
using namespace std;
long long f[40005][45][45],a[20005],b[20005],c[20005];
int son[20005][2],n;
void dfs(int u,int x,int y)
{
 if(u>n)
 {
  u-=n;
  for(int i=0;i<=x;i++)
   for(int j=0;j<=y;j++)
    f[u+n][i][j]=c[u]*(a[u]+i)*(b[u]+j);
  return;
 }
 dfs(son[u][0],x+1,y);
 dfs(son[u][1],x,y+1);
 for(int i=0;i<=x;i++)
  for(int j=0;j<=y;j++)
   f[u][i][j]=min(f[son[u][0]][i+1][j]+f[son[u][1]][i][j],f[son[u][0]][i][j]+f[son[u][1]][i][j+1]);
}
int main()
{
 ios::sync_with_stdio(false);
 cin>>n;
 for(int i=1;i<n;i++)
 {
  cin>>son[i][0]>>son[i][1];
  if(son[i][0]<0)son[i][0]=-son[i][0]+n;
  if(son[i][1]<0)son[i][1]=-son[i][1]+n;
 }
 for(int i=1;i<=n;i++)
  cin>>a[i]>>b[i]>>c[i];
 dfs(1,0,0);
 cout<<f[1][0][0]<<endl;
 return 0;
}