E - Bichrome Tree

E - Bichrome Tree

解法
木のdpを考えたくなる

頂点iの色をai、違う色をbiとする
頂点i以下でaiの合計はXiであり、biの合計は自由である

よってdp[i][bsum] := i以下でbiの合計がbsumとなるものが作れるか
としたくなったが、計算量が多すぎる

ここでbsumは小さければ小さいほど都合がいいという事に気付けると
a[i] = asum
b[i] = bsum
として各iで、子の頂点達を上手くaiかbiに割り振り、それらのaiの合計がXi以下(iの重みをXi - aiとすれば成り立つため) かつbiの合計を最小にする問題になる

Sign In - AtCoder

digraph<> g(2 * k5);
vi l(5050), r(5050);

bool ds(int i) {
    forg(gi, g[i])if (!ds(t))return 0;
    fill(l, linf);
    l[0] = 0;
    forg(gi, g[i]){
        fill(r,linf);
        rep(x,5050){
            if(l[x]==linf)continue;
            //親と同じ色
            chmin(r[min(5001,x+a[t])],min(l[x]+b[ t],5001 ));
            //違う色
            chmin(r[min(5001,x+b[t])],min(l[x]+a[ t],5001));
        }
        swap(l,r);
    }
    a[i] = c[i];
    b[i] = linf;
    rep(x,c[i]+1)chmin(b[i], l[x]);
    return b[i] != linf;
}

void solve() {
    cin >> n;
    rep(i, 1, n)g.add(in() - 1, i);
    na(c, n);
    if (ds(0)) {
        cout << "POSSIBLE" << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}

||