Description

给出一棵含有 \(n\) 个叶子节点的二叉树，对于每个非叶子节点的节点，其与左儿子相连的边为公路，其与右儿子相连的边为铁路。对于每个节点，选择一条与其儿子相连的铁路或公路。对于每个叶子节点 \(u\) ，含有三个参数 \(a,b,c\) ，记 \(u\) 到根节点一共需要经过 \(x\) 条未选择的公路与 \(y\) 条未选择的铁路，其代价为

\[c_u \cdot (a_u + x) \cdot (b_u + y)\]

求最小的总代价和。

\(n \le 20000\) ， \(1 \le a_i,b_i \le 60\) ， \(1 \le c_i \le 10^9\) ，二叉树深度不超过 \(40\) 。

Solution

传说中的普及 \(dp\) 。

记 \(f_{i,j,k}\) 为 \(i\) 这个节点到根节点路径上一共需要经过 \(j\) 条未选择的公路与 \(k\) 条未选择的铁路，其子树中最小的代价和。

答案就是 \(f_{1,0,0}\) 。

转移就是考虑当前节点选择铁路还是选择公路。

时间复杂度和空间复杂度为 \(O(40^2n)\) 。

Code

#include 
    
     #define ll long long#define F(o, i, j) (1ll*c[o]*(i+a[o])*(j+b[o]))using namespace std;const int N = 20000+5;int n, a[N], b[N], c[N], ls[N], rs[N];ll f[N][41][41];void dfs(int o, int dep) {    if (o < 0) return;    int l = ls[o], r = rs[o];    dfs(l, dep+1), dfs(r, dep+1);    for (int i = 0; i <= dep; i++)    for (int j = 0; j <= dep; j++) {        if (l < 0 && r < 0) f[o][i][j] = min(F(-l, i+1, j)+F(-r, i, j), F(-l, i, j)+F(-r, i, j+1));        else if (l < 0) f[o][i][j] = min(F(-l, i+1, j)+f[r][i][j], F(-l, i, j)+f[r][i][j+1]);        else if (r < 0) f[o][i][j] = min(f[l][i+1][j]+F(-r, i, j), f[l][i][j]+F(-r, i, j+1));        else f[o][i][j] = min(f[l][i+1][j]+f[r][i][j], f[l][i][j]+f[r][i][j+1]);    }}void work() {    scanf("%d", &n);    memset(f, 127/3, sizeof(f));    for (int i = 1; i < n; i++) scanf("%d%d", &ls[i], &rs[i]);    for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]);    dfs(1, 0);    printf("%lld\n", f[1][0][0]);}int main() {work(); return 0; }