AtCoder Regular Contest 083 E - Bichrome Tree

http://arc083.contest.atcoder.jp/tasks/arc083_c

問題概要

N頂点の根付き木とN要素の数列Xが与えられる。木の各頂点に白or黒の色と非負整数を割り当てるとき、頂点nを根とする部分木に含まれる頂点のうちnと同じ色のものに割り当てられた数の合計がX_nとなるような割り当てが可能かどうか判定せよ。

N <= 1000

X <= 5000

解法

dp(n): 頂点nを根とする部分木において、片方の色の合計をXnとしたときのもう片方の色の合計の最小値

このdpを葉の方から更新していく。ただし葉の場合は0を返すことにする。葉でない頂点nのdp(n)を計算する際には、nのすべての子mについて、Xmとdp(m)のどちらかをどちらかの色に塗る、の組み合わせ列挙を考えるとdp(n)を出すことができる。普通にやると2^子の数の計算量がかかってしまうが、X<=5000を利用してナップサックDPをやると「片方の色の合計がxであるときのもう片方の色の合計の最小」をO(NX)で出すことができる。このときどうやってもどちらの色もXn以下にできないのであれば、nに非負整数を割り当てることはできず答えはIMPOSSIBLEとなる。

感想

説明が難しすぎる

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
immutable int INF = 1 << 29;
 
bool solve() {
    auto N = readln.chomp.to!int;
    auto P = readln.split.map!(to!int).array;
    auto X = readln.split.map!(to!int).array;
    auto edges = new int[][](N);
    foreach (i; 0..N-1) {
        edges[i+1] ~= P[i]-1;
        edges[P[i]-1] ~= i+1;
    }
 
    int dfs(int n, int p) {
        auto dp = new int[][](2, X[n]+1);
        int cur = 0, tar = 1;
        dp[cur].fill(INF);
        dp[cur][0] = 0;
 
        foreach (m; edges[n]) {
            if (m == p) continue;
            dp[tar].fill(INF);
            int w = dfs(m, n);
            int b = X[m];
            foreach (i; 0..X[n]+1) {
                if (dp[cur][i] != INF) {
                    if (i + w <= X[n]) {
                        dp[tar][i+w] = min(dp[tar][i+w], dp[cur][i]+b);
                    }
                    if (i + b <= X[n]) {
                        dp[tar][i+b] = min(dp[tar][i+b], dp[cur][i]+w);
                    }
                }
            }
 
            cur ^= 1, tar ^= 1;
        }
 
        return dp[cur].reduce!min;
    }
 
    return dfs(0, -1) != INF;
}
 
void main() {
    writeln( solve ? "POSSIBLE" : "IMPOSSIBLE" );
}