测试地址：道路 做法：本题需要用到树形DP。 去掉题目的各种包装，我们发现整棵树就是棵二叉树，城市就是非叶子节点，乡村是叶子节点。 看到这种树上最优化的问题，一般都会先想到树形DP。一个显然的思路是定义 f(i) f ( i ) 为以点 i i 为根的子树的最小不便利值，然后在每个点上进行决策，即决定翻修到达该点的公路还是铁路，更新答案。但是我们很快发现一个问题，一棵子树的最小不便利值和并不仅仅跟子树内的信息有关，还和从它到根的路径上翻修的情况有关。我们发现题目的数据范围中有一个条件：树的深度不超过4040，那么我们就可以设 f(i,j,k) f ( i , j , k ) 为在从 i i 到根的路径上，有jj条公路和 k k 条铁路没有翻修的情况下，以ii为根的子树的最小不便利值。这样我们就可以很轻易地得出状态转移方程了，最后的答案显然为 f(1,0,0) f ( 1 , 0 , 0 ) ，时间复杂度为 O(n(depth)2) O ( n ( d e p t h ) 2 ) 。 这题有点卡空间，要注意优化一下空间，例如叶子节点的 f f 可以不用存下，直接在用到时就可以O(1)O(1)算出。 以下是本人代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,ch[20002][2],tot=0; ll f[20002][42][42],a[20002],b[20002],c[20002]; ll F(int v,ll x,ll y) { if (v<0) return c[-v]*(a[-v]+x)*(b[-v]+y); else return f[v][x][y]; } void dp(int v,ll x,ll y) { if (v>0) { dp(ch[v][0],x+1,y); dp(ch[v][1],x,y+1); for(ll i=0;i<=x;i++) for(ll j=0;j<=y;j++) { f[v][i][j]=F(ch[v][0],i+1,j)+F(ch[v][1],i,j); f[v][i][j]=min(f[v][i][j],F(ch[v][0],i,j)+F(ch[v][1],i,j+1)); } } } int main() { scanf("%d",&n); for(int i=1;i<n;i++) scanf("%d%d",&ch[i][0],&ch[i][1]); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i],&b[i],&c[i]); dp(1,0,0); printf("%lld",f[1][0][0]); return 0; }