ABC036 D 塗り絵 - 足跡-sokuseki-

はじめての木DPです。

$N$ 頂点の木が与えられる。
両端の頂点が黒で塗られるような辺がないように、頂点を白または黒でぬるとき、塗り方の通り数を $10^9 + 7$ で割ったあまりを答えよ。

制約
$1 \le N \le 10^5$

漸化式を立てて木の上でDPをしましょう。

$f( x )$ := 頂点 $x$ を親とする部分木に含まれる頂点をすべて白または黒で塗り、両端が黒で塗られた辺が存在しないようにする方法の通り数。
$g( x )$ := $f( x )$ と同じ。ただし、頂点 $x$ は必ず白で塗らなければならない。

とすると、以下の2つの漸化式を作れる(ただし、 $y_1 , y_2 , … , y_k$ は $x$ の子とする)。

なぜこの漸化式がつくれるのかは、次のサイトがわかりやすいです、これで理解しました。
漸化式を立てて「tree DP問題」を解く D - 塗り絵 - マツシタケイタの技術ブログ(勉強中)

あとは、木の葉から順番に $f( x )$ と $g( x )$ を埋めていくことで、 $O(N)$ で求められる。
葉から根にむかって順番に求めるには、dfsをつかって根まで行き、帰りがけに計算すればよい。