問題：競プロ典型 90 問 073 - We Need Both a and b（★5）
解説
以下の木DPを構築して解きたい。
dp[u][j] := （頂点uを根とする部分木において、）頂点uを含む連結成分の状態がjのときの場合の数。ただしj=0は'a'しかない状態、j=1は'b'しかない状態、j=2は'ab'両方ある状態
詳しい解説は公式解説やこちらの記事に任せるとして、dpの更新式の勘所のみを解説したい。
dp[u][0]の更新式の考え方
- 頂点uが'a'の場合、
- (1)子の連結成分が'a'の状態かつ、連結している
- (2)子の連結成分が'ab'の状態かつ、連結していない
「(1)子の連結成分が'a'の状態かつ、連結している」のパターンは明らかにOKである。なぜなら、子の連結成分が'a'の状態で頂点uと連結していれば、頂点uは'a'の状態のままだからである。
「(2)子の連結成分が'ab'の状態かつ、連結していない」のパターンも明らかにOKである。なぜなら、子の連結成分が'ab'の状態なら問題の制約上連結しなくてもOKであり、頂点uは'a'の状態のままだからである。
他のパターンも考えてみる。たとえば、「子の連結成分が'b'の状態かつ、連結していない」パターンはなぜ足しては駄目なのか。これだと「子の連結成分が'b'の状態のまま」になってしまい、これは問題の制約上「どの連結成分も'ab'の状態になっていなければならない」を満たせないからである。
dp[u][2]の更新式の考え方
- 頂点uが'a'の場合、
- (1)子の連結成分が'ab'の状態かつ、連結している
- (2)子の連結成分が'b'の状態かつ、連結している
- (3)子の連結成分が'a'の状態かつ、連結している
- (4)子の連結成分が'ab'の状態かつ、連結していない
「(1)子の連結成分が'ab'の状態かつ、連結している」のパターンは明らかにOKである。なぜなら、子の連結成分が'ab'の状態で頂点uと連結していれば、頂点uは状態'ab'になるからだ。
「(2)子の連結成分が'b'の状態かつ、連結している」のパターンも明らかにOKである。 なぜなら、子の連結成分が'b'の状態で頂点uと連結していれば、頂点uは状態'ab'になるからだ。
「(3)子の連結成分が'a'の状態かつ、連結している」のパターンはなぜOKなのか。子の連結成分が'a'の状態で頂点uと連結すると頂点uは状態'a'のままだ。しかし、他の子の部分木がひとつでも(1)(2)のパターンであれば、頂点uは状態'ab'になれるので、(3)のパターンを含んでもよい。 ただし、他の子の連結成分も状態'a'の場合や(4)のパターンの場合、頂点uは'a'の状態のままである。なのでこの状態はあとから引かなければならない（★1）。
「(4)子の連結成分が'ab'の状態かつ、連結していない」のパターンはなぜOKなのか。問題の制約上、子の連結成分が'ab'の状態であるなら、連結していなくてもOKであり、頂点uは他の子の連結成分と連結して'ab'状態になれればOKだからだ。ただし、他の子の連結成分も(4)のパターンの場合、頂点uは'a'の状態のままである。なのでこの状態はあとから引かなければならない（★2）。
あとから引く(★1)+(★2)の場合の数とは、「頂点uが'a'の状態」のことであり、それはdp[u][0]のことに他ならない。
