2014-08-27

Codeforces #263 Div2 D. Appleman and Tree

16:22 |

ノードが白か黒に塗られた木が与えられる。辺を任意個消した時にできる部分木がすべて１個だけ黒を含むようにする方法は何通りあるか？ (mod 10^9+7 で)
2≦|ノード数|≦10^5

黒-黒-黒なら２箇所切るの1通り
黒-白-黒なら白の左右どっちか切ればいいので2通り
(node, nodeを含めて上の区切られたエリアの中に黒があるかどうか) -> 何通りの木DPかな
- (後から考えるとこれじゃ部分問題にならない... というか上ってどこまでだよ)
(root, なし)が答えかな
今までどうだったかに応じて子ノードそれぞれつなぐべきか切るべきかとかで掛けたり足したりすれば良さそう
式らしきものができた→実装→ sample 1 が合わない →(5分前) あ、分配できないのにできる前提でやってた

おわた

kawatea さんのとか読む
http://codeforces.com/contest/461/submission/7588134

状態は f(node, nodeとnodeの子以下の黒の個数) -> 何通り
で、ノードが白で黒の個数が1になるような時だけ全子ノードに対してさらにDPしている。
だいたい理解

いろいろ考えた結果
状態を g(node, i, nodeとnodeのi番目までの子以下の黒の個数) -> 何通り
とするとさらに簡潔になりそう


i番目の子と node を含む領域をつなぐなら ---, 切るなら -|- として、

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


なので
c0 = g(i番目の子, all, なし)
c1 = g(i番目の子, all, あり)
と置くと

g(node, i, なし) = g(node, i-1, なし) * (c0+c1)
g(node, i, あり) = g(node, i-1, なし) * c1 + g(node, i-1, あり) * (c0+c1)
となる.

初期条件は
g(node, 0, なし) = nodeが白 ? 1 : 0
g(node, 0, あり) = nodeが黒 ? 1 : 0

知りたい答えは g(root, all, あり)

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] = {1, 0}; // modll 略
	dp[0] = (modll)!black[idx];
	dp[1] = (modll)black[idx];
	REP(i, g[idx].size()) {
		int ni = g[idx][i];
		if(prev==ni) continue;
		ll c0 = dfs(idx, ni, 0);
		ll c1 = dfs(idx, ni, 1);
		modll n0 = dp[0] * (c0+c1);
		modll n1 = dp[0] * c1 + dp[1] * (c0+c1);
		dp[0] = n0;
		dp[1] = n1;
	}
	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;
}

kojingharangの日記

2014-08-27

Codeforces #263 Div2 D. Appleman and Tree