E - Attack to a Tree

atcoder.jp

2乗の木dp
なのでdpのサイズは気にしなくていい

切り離したものは条件を満たしていないといけないが、今見ている連結成分は後々マージされるためその限りではない
Submission #4131219 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

int dp[5000][5001][2],sub[5001][2];
//vvi(sub, 5050, 2);
undigraph<> g(0);
vi es(5050);

void ds(int i, int p) {
    forg(gi, g[i])if (t != p)ds(t, i);
    int sum = 0;
    dp[i][0][a[i] < 0] = a[i];
    forg(gi, g[i]) {
            if (t == p)continue;
            rep(ci, sum + 1) {
                rep(ct, es[t] + 1) {
                    rep(ki, 2) {
                        rep(kt, 2) {
                            //繋ぐ
                            if (dp[i][ci][ki] < linf && dp[t][ct][kt] < linf)
                                chmin(sub[ci + ct][ki || kt], dp[i][ci][ki] + dp[t][ct][kt]);
                            //切る
                            if (dp[t][ct][kt] < 0 || (!kt && dp[t][ct][kt] != linf))
                                chmin(sub[ci + ct + 1][ki], dp[i][ci][ki]);
                        }
                    }
                }
            }
            sum += es[t] + 1;
            rep(j, sum + 1)
                rep(k, 2) {
                    dp[i][j][k] = sub[j][k];
                    sub[j][k] = linf;

                }
        }
    es[i] = sum;
}