kojingharangの日記

Codeforces #253 Div2 D. Appleman and Tree （より原理的にしてみる）

18:02 |

• 昨日のやつ https://topcoder-g-hatena-ne-jp.jag-icpc.org/kojingharang/20140827 の↓の図は人間が検討しなくてもいい内容だよな、と思ったので、そこもコードにしたらさらに簡潔になるんじゃないか、やってみようの巻き。

g(node, i, なし) は
  g(node, i-1, なし) × --- g(i番目の子, all, なし) ... OK
+ g(node, i-1, なし) × -|- g(i番目の子, all, なし) ... だめ(i番目の子以下が黒なしで確定しちゃう
+ g(node, i-1, なし) × --- g(i番目の子, all, あり) ... だめ
+ g(node, i-1, なし) × -|- g(i番目の子, all, あり) ... OK
+ g(node, i-1, あり) × --- g(i番目の子, all, なし) ... だめ
+ g(node, i-1, あり) × -|- g(i番目の子, all, なし) ... だめ(i番目の子以下が黒なしで確定しちゃう
+ g(node, i-1, あり) × --- g(i番目の子, all, あり) ... だめ
+ g(node, i-1, あり) × -|- g(i番目の子, all, あり) ... だめ

g(node, i, あり) は
  g(node, i-1, なし) × --- g(i番目の子, all, なし) ... だめ
+ g(node, i-1, なし) × -|- g(i番目の子, all, なし) ... だめ
+ g(node, i-1, なし) × --- g(i番目の子, all, あり) ... OK
+ g(node, i-1, なし) × -|- g(i番目の子, all, あり) ... だめ
+ g(node, i-1, あり) × --- g(i番目の子, all, なし) ... OK
+ g(node, i-1, あり) × -|- g(i番目の子, all, なし) ... だめ
+ g(node, i-1, あり) × --- g(i番目の子, all, あり) ... だめ
+ g(node, i-1, あり) × -|- g(i番目の子, all, あり) ... OK

• Accepted in Practice room
• 問題の条件をよりそのままコードに落とした感は出てきたが、全体的に簡潔さはあんまし変わってない気がする。。

VVI g;
VVI memo;
vector<bool> black;

// g(idx, all, b)
ll dfs(int prev, int idx, int b) {
	if(memo[b][idx]>=0) return memo[b][idx];

	// このノードと子ノード[0-i]以下からなる subtree を条件を満たすように区切ったとき, node を含む領域に含まれる黒の数 -> 何通り
	modll dp[2];
	dp[0] = (modll)!black[idx];
	dp[1] = (modll)black[idx];
	REP(i, g[idx].size()) {
		int ni = g[idx][i];
		if(prev==ni) continue;
		modll ndp[2] = {0, 0};
		modll ch[2] = {dfs(idx, ni, 0), dfs(idx, ni, 1)};
		REP(pi, 2) REP(ci, 2) REP(cut, 2) {
			int obi = pi + (cut ? 0 : ci);
			if(cut && ci==0) continue; // 切断して子以下に黒がなかったらだめ
			if(obi < 2) ndp[obi] += dp[pi] * ch[ci];
		}
		dp[0] = ndp[0];
		dp[1] = ndp[1];
	}
	return memo[b][idx] = dp[b];
}

int main() {
	ll N,p,v;
	while(cin>>N) {
		g = VVI(N);
		memo = VVI(2, VI(N, -1));
		black = vector<bool>(N);
		REP(i, N-1) {
			cin>>p;
			g[i+1].PB(p);
			g[p].PB(i+1);
		}
		REP(i, N) {
			cin>>v;
			black[i] = v;
		}
		ll ans = dfs(-1, 0, 1);
		cout<<ans<<endl;
	}
	
	return 0;
}

ツイートする