Description：

一个国家有 $n-1$ 个城市和 $n$ 个乡村构成一棵树，乡村是叶子，每个城市最多有 $2$ 个出边，一个公路一个铁路，可以翻新每个城市的一条入边，第 $i$ 个乡村的代价为 $c_i\times (a_i+从i到根未翻修的公路个数)\times(b_i+从i到根未翻修的铁路个数)$ ，最小化总代价。

$1\leqslant n \leqslant 20000$ ，保证每个乡村到根只有不超过 $40$ 条路。

Solution：

这个题运用了动态规划的一个重要思想，就是先预先对未来的决策做出一些承诺，然后在状态里把这个承诺记下来，让以后的转移去实现。

设 $f[k][i][j]$ 表示从根到 $k$ 未翻修的公路有 $i$ 个，铁路有 $j$ 个的最小代价，既然从每个乡村到根只有不到 $40$ 条路，那么完全可以开一个 $f[20000][40][40]$ 把它记下来，最后的答案就是 $f[1][0][0]$ ，转移为 $f[k][i][j]=\min(f[s[k]][i][j]+f[t[k]][i][j+1],f[s[k]][i][j+1]+f[t[k]][i][j])$ ，记忆化搜索比较容易写。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 20010

typedef long long ll;

ll s[MAXN],t[MAXN];

ll a[MAXN],b[MAXN],c[MAXN];

ll f[MAXN][41][41];

ll dp(int k,int x,int y)

{

	if(k < 0)

	{

		int t = -k;

		return c[t] * (a[t] + x) * (b[t] + y);

	}

	if(f[k][x][y] != -1)return f[k][x][y];

	return f[k][x][y] = min(dp(s[k],x,y) + dp(t[k],x,y + 1),dp(s[k],x + 1,y) + dp(t[k],x,y));

}

int main()

{

	memset(f,-1,sizeof(f));

	scanf("%d",&n);

	for(int i = 1;i <= n - 1;++i)

	{

		scanf("%d%d",&s[i],&t[i]);

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d",&a[i],&b[i],&c[i]);

	}

	cout << dp(1,0,0) << endl;

	return 0;

}