「Bzoj 5290」「Hnoi2018」道路 (树形DP+卡空间)

BZOJ 5290
题意：见上。
一开始没看见必须选边…
然后发现是树形DP然后打……
之后发现我写假了
我们直接设$dp(u,i,j)$为$u$到根经过$i$条绿边，$j$条红边的最小代价
那么转移即
$$
dp[u][i][j] = \min(dp[lc[u]][i][j] + dp[rc[u]][i][ + 1], dp[lc[u]][i + 1][j] + dp[rc[u]][i][j])
$$

然后这题一个精髓是卡空间方法，我们维护一个dfn，然后每次存两个孩子的值即可，具体可看代码。

知识点
1、dfn卡空间方法

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 40000 + 5, INF = 1e16;

    LL grn[MAXN], red[MAXN], dp[105][55][55];
    LL n, dfn[MAXN];
    LL a[MAXN], b[MAXN], c[MAXN];

    void dfs(LL u, LL now) {
        dfn[u] = now;  // 卡空间
        if (u > n - 1) {
            for (LL i = 0; i <= 41; ++i) 
            for (LL j = 0; j <= 41; ++j) dp[dfn[u]][i][j] = c[u] * (a[u] + i) * (b[u] + j);
            return ;
        }
        dfs(red[u], now + 1), dfs(grn[u], now + 2); // 卡空间
        for (LL i = 0; i <= 41; ++i) 
        for (LL j = 0; j <= 41; ++j) {
            dp[dfn[u]][i][j] = min(dp[dfn[grn[u]]][i][j] + dp[dfn[red[u]]][i][j + 1], dp[dfn[grn[u]]][i + 1][j] + dp[dfn[red[u]]][i][j]);
        }
    }

    void clean() {
        ms(red, 0), ms(grn, 0);
        for (int i = 0; i <= 101; ++i)
        for (int j = 0; j <= 51; ++j)
        for (int k = 0; k <= 51; ++k) dp[i][j][k] = INF;
    }
    int solve() {

        clean();
        cin >> n;
        for (LL s, t, i = 1; i < n; ++i) {
            scanf("%lld%lld", &s, &t);
            if (s < 0) s = -s + n - 1;
            if (t < 0) t = -t + n - 1;
            grn[i] = s, red[i] = t;
        }
        for (LL i = 1; i <= n; ++i) scanf("%lld%lld%lld", &a[i + n - 1], &b[i + n - 1], &c[i + n - 1]);

        dfs(1, 1);

        LL ans = INF;
        for (LL i = 0; i <= 41; ++i) 
        for (LL j = 0; j <= 41; ++j) ans = min(ans, dp[dfn[1]][i][j]);

        cout << ans;

        return 0;
    }
}
int main() { 
    flyinthesky::solve();
    return 0;
}