DP P
与えられた木を白黒で塗り分ける、黒い頂点は隣接してはいけない、何通りあるか数え上げよ、という問題
直線的な依存関係の時に「端から順に」「直前だけ見て」DPができたのと同様に、木構造の依存関係の時には「葉から順に」「木の根だけ見て」DPができる 木DP https://gyazo.com/10a0e781f27b7b7fc988257afad814b8
木をたどるところで再帰を使っているが、対象が木であって合流がないのでメモ化再帰にする必要はない
code:python
def solve(N, edges):
def visit(parent, self):
if parent != 0 and len(edgesself) == 1: # self is leaf
return (1, 2) # white, total
black = 1
white = 1
if child == parent:
continue
w, t = visit(self, child)
black *= w
black %= MOD
white *= t
white %= MOD
ret = (white, white + black)
return ret
return visit(0, 1)1 % MOD Cython