割と面白かった。
http://codeforces.com/contest/482/problem/D
問題
根付木の構造が与えられる。
初期値で全頂点の色は赤である。
ここに根から以下のDFSで頂点に色を塗る。
- 今いる頂点を、今まで色を塗った数が偶数なら白、奇数なら黒で塗る。
- 半分の確率でsubtreeを頂点番号の大きい順、残り半分の確率で番号の小さい順にたどる。
- 上記順序に応じて、subtreeをDFSする。ただし各子に対しDFSを行う確率は1/2である。
最終的に構築される木の色の状態は何通りか。
解法
確率を答える問題ではないので、確率云々は忘れてよい。要は
- subtreeは番号の昇順と降順両方でたどる場合を考える
- 各子はたどる場合とたどらない場合を考える
である。
この問題は、子から順に色を塗る数が奇数または偶数となる塗り方を木DPで計算していけば良い。
木DPはとりあえず頂点番号が昇順となるように行い、最後にそれを倍にすればよい。
ただし頂点番号を辿る順が昇順でも降順でも色の配置が変わらないケースがあるので、その分は倍にならないようにするケースがある。
色の配置が変わらないのは以下のケース。
- subtree全体で偶数個の頂点を塗り、うちsubtreeの根から伸びる子のsubtreeはすべて偶数個色を塗っている場合。
- subtree全体で奇数個の頂点を塗り、うちsubtreeの根から伸びる子のsubtreeはすべて奇数個色を塗っており、かつ奇数個塗ったsubtreeは奇数個ある場合。
よって木DPの際、全て偶数個の頂点を色を塗るパターンと、奇数個の頂点の色を塗るパターンの登場回数を偶数回・奇数回それぞれ管理していく必要がある。
int N; vector<int> V[100500]; ll mo=1000000007; ll dp[100500][2]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) cin>>x, V[x-1].push_back(i+1); for(i=N-1;i>=0;i--) { ll alleven=1,odd_even=1,odd_odd=0; dp[i][0]=0; //even dp[i][1]=1; //odd FOR(j,V[i].size()) { x=V[i][j]; ll a=dp[i][0],b=dp[i][1]; dp[i][0]=(a*(1+dp[x][0])+b*dp[x][1])%mo; dp[i][1]=(a*dp[x][1]+b*(1+dp[x][0]))%mo; alleven=(alleven*(1+dp[x][0]))%mo; a=odd_even,b=odd_odd; odd_even=(a+b*dp[x][1])%mo; odd_odd=(b+a*dp[x][1])%mo; } dp[i][0]=(dp[i][0]*2+(mo-odd_odd))%mo; dp[i][1]=(dp[i][1]*2+(mo-alleven))%mo; } cout << (dp[0][0]+dp[0][1])%mo << endl; }
まとめ
色を塗る数の偶奇で分けるDPは思いついたけど、ひっくり返しても色の配置が変わらないケースをうまく自前で管理できなかった。
