漸化式を立てて「tree DP問題」を解く D - 塗り絵
問題
D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder
N 個の島があります。 島には 1 から N までの番号がついています。 また、N−1 個の橋があります。 i 番目の橋は ai 番の島と bi 番の島をつないでいます。 どの島からどの島へも橋をいくつか経由して到達できることがわかっています。
すぬけ君は、それぞれの島を白または黒に塗ることにしました。 ただし、両端の島が黒で塗られているような橋があってはいけません。 色の塗り方が何通りあるか、109+7 で割った余りを求めてください。
解説を読む
http://abc036.contest.atcoder.jp/data/abc/036/editorial.pdf
まず、ｘとｙを以下のように定義する。
- x := 任意の頂点
- y := 頂点ｘの子ノード(k個存在する場合はy1, y2, ..., ykとなる)
また、f(x)とg(x)を以下のように定義する。
- f(x) := 頂点 x を親とする部分木に含まれる頂点をすべて白または黒で 塗り，両端が黒で塗られた辺が存在しないようにする方法の通り数
- g(x) := f(x)と同じ。ただし。頂点 x は必ず白で塗らなければならない。
上記について具体的に思考してみる。
後は立てた漸化式を解くようにコードを書く。
