这道题题目描述很长……不过我们需要静下来仔细看看题，其实题目并没有那么难。（虽然说是bin哥讲的）
我们发现，首先这个树的深度不是很大，最多不会超过40，那么我们可以以此作为一个突破口进行分析。之后我们又发现，你能修改的，只是所有非叶子结点所连的两条边之中的一条，而且树是一棵完全二叉树。
所以我们直接考虑用dp[x][l][r]表示在第x个点，走过l条公路，r条铁路到达1号节点的最小花费，那么就有dp[x][l][r] = min(dp[lc[x]][l+1][r] + dp[rc[x]][l][r],dp[lc[x]][l][r] + dp[rc[x]][l][r+1]),也就是修左边或者右边的道路的情况。
这个可以使用记忆化搜索实现（记忆化搜索真的强），我们在搜到村庄的时候，就直接返回计算的值。最后的答案是dp[1][0][0].
这道题好像卡空间，但是……我直接交是能过的，开O2反而会T一个点。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 1000005; const int N = 20005; const int INF = 1000000009; const double eps = 1e-4; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } ll dp[N][50][50],n,lc[N],rc[N],a[N],b[N],c[N],maxn; ll dfs(ll x,ll l,ll r) { if(x > n) return c[x-n] * (a[x-n] + l) * (b[x-n] + r); if(dp[x][l][r] != -1) return dp[x][l][r]; dp[x][l][r] = dfs(lc[x],l+1,r) + dfs(rc[x],l,r); dp[x][l][r] = min(dp[x][l][r],dfs(lc[x],l,r) + dfs(rc[x],l,r+1)); return dp[x][l][r]; } int main() { n = read(); rep(i,1,n-1) { lc[i] = read(),rc[i] = read(); if(lc[i] < 0) lc[i] = -lc[i] + n; if(rc[i] < 0) rc[i] = -rc[i] + n; } rep(i,1,n) a[i] = read(),b[i] = read(),c[i] = read(); memset(dp,-1,sizeof(dp)); dfs(1,0,0); printf("%lld ",dp[1][0][0]); //rep(i,0,n-1) maxn = max(maxn,dp[1][i][n-1-i]); //printf("%lld ",maxn); return 0; }