Ecasdqina's MEMO

-!=x=!-

ゆふふ．

もうひとつのるま式全方位木 DP

DP tutorial

前提知識

もうひとつのるま式全方位木 DP とは

るま式全方位木 DP では逆元が必要でした． しかし全方位木 DP は両側累積和を用いることで逆元を使わずに書くことが出来ます． そこで，るま式全方位木 DP を少し改造することで逆元が必要無いように書き換えたものを，ぼくが勝手にもうひとつのるま式全方位木 DP と呼んでいます．

実装例

std::vector<std::map<int, value>> dp(n);
auto solve = [&](auto&& solve, int v, int par, bool flag) -> value {
    if(dp[v].count(par)) return dp[v][par];

    value res = id; // id = 単位元
    if(par == -1 or flag) {
        std::vector<value> ret;
        for(int i = 0; i < g[v].size(); i++) {
            int to = g[v][i];
            if(to == par) continue;
            
            ret.push_back(solve(solve, to, v, flag));
        }
        
        std::vector<value> R(ret.size() + 1, id);
        for(int i = R.size() - 1; i > 0; i--) R[i - 1] = merge(R[i], ret[i - 1]);
        if(par == -1) {
            value L = id;
            for(int i = 0; i < g[v].size(); i++) {
                int to = g[v][i];
                
                dp[v][to] = merge(L, R[i + 1]);
                L = merge(L, ret[i]);
            }
        }

        res = R[0];
    } else {
        solve(solve, v, -1, flag);

        return solve(solve, v, par, flag);
    }

    return dp[v][par] = res;
};
solve(solve, 0, -1, true);

for(int i = 0; i < n; i++) cout << solve(solve, i, -1, false) << endl;

問題例