Bichrome Tree [AtCoder Regular Contest 083 E]

https://beta.atcoder.jp/contests/arc083/tasks/arc083_c

解説

https://beta.atcoder.jp/contests/arc083/submissions/1599845

木DPをする。
dp[cu][white=0|black=1] := 頂点cuがwhite|blackである時に、頂点cuの部分木で逆の色に書いてある数の総和の最小値
各頂点で白にでも黒にでもできる子供があった場合は、更にDPをして答えを作る。

#define INF INT_MAX/2
int N, X[1010];
vector<int> E[1010];
//---------------------------------------------------------------------------------------------------
#define YES "POSSIBLE"
#define NO "IMPOSSIBLE"
string ans = YES;
int dp[1010][2];
void dfs(int cu, int pa = -1) {
    int white = 0, black = 0;
    vector<int> any;
    fore(to, E[cu]) if (to != pa) {
        dfs(to, cu);
 
        // どっちもダメはダメ
        if (dp[to][0] == INF && dp[to][1] == INF) { ans = NO; return; }
 
        if (dp[to][0] == INF) { // 子供は1(=黒)しかなれない
            white = dp[to][1];
            black = X[to];
        } else if (dp[to][1] == INF) { // 子供は0(=白)しかなれない
            white = X[to];
            black = dp[to][1];
        } else { // どっちもOK
            any.push_back(to);
        }
    }
 
    // whiteをblack最小で作る
    vector<int> dp2(5050, INF);
    dp2[white] = black;
    fore(ch, any) {
        vector<int> pd2(5050, INF);
        rrep(i, 5000, 0) if (dp2[i] != INF) {
            // white採用
            if(i + X[ch] < 5050) pd2[i + X[ch]] = min(pd2[i + X[ch]], dp2[i] + dp[ch][1]);
            if (i + dp[ch][0] < 5050) pd2[i + dp[ch][0]] = min(pd2[i + dp[ch][0]], dp2[i] + X[ch]);
        }
        swap(dp2, pd2);
    }
    rep(i, 0, X[cu] + 1) if (dp2[i] != INF) dp[cu][0] = min(dp[cu][0], dp2[i]);
 
    // 逆
    dp2.resize(5050, INF);
    dp2[black] = white;
    fore(ch, any) {
        vector<int> pd2(5050, INF);
        rrep(i, 5000, 0) if (dp2[i] != INF) {
            if (i + X[ch] < 5050) pd2[i + X[ch]] = min(pd2[i + X[ch]], dp2[i] + dp[ch][0]);
            if (i + dp[ch][1] < 5050) pd2[i + dp[ch][1]] = min(pd2[i + dp[ch][1]], dp2[i] + X[ch]);
        }
        swap(dp2, pd2);
    }
    rep(i, 0, X[cu] + 1) if (dp2[i] != INF) dp[cu][1] = min(dp[cu][1], dp2[i]);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N) {
        int P; cin >> P; P--;
        E[i].push_back(P);
        E[P].push_back(i);
    }
    rep(i, 0, N) cin >> X[i];
    rep(i, 0, N) rep(j, 0, 2) dp[i][j] = INF;
 
    dfs(0);
 
    if (dp[0][0] == INF && dp[0][1] == INF) ans = NO;
 
    //rep(i, 0, N) rep(j, 0, 2) printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
 
    cout << ans << endl;
}