Codeforces 630 F Independent Set
はじめに
マジでE問題場合分けを忘れて全てを破滅させた．ドドドドドドドちくしょう
そしてこの問題を頑張って解きましたが，コードは汚く，考え方もスマートであるととても思えないのでもっといい方針があるのだろうと思います．
問題概要
https://codeforces.com/contest/1332/problem/F
木の空ではない全ての辺集合について，辺集合の辺と全ての辺が結ぶ頂点からなる部分グラフを作り，独立集合の個数を求め，総和を求める．
考えたこと
まずこの問題を読み終えたときに，「木の頂点を白黒二色で塗るとき，辺の両端が黒にならないように塗る塗り方は何通り？」みたいな問題を昔やったような気がして，それを思い出していました．その問題は各頂点ごと，その頂点を黒で塗る場合と白で塗る場合で数え上げる木DPで解いた気がします．
ですので，この問題も似たような方針がとれないか検討しました．紆余曲折あったあと，この問題でも独立集合を黒が隣り合わないような頂点の塗り方と言い換え，各頂点について，その頂点が，黒である，白である，使わない，それぞれの場合のその頂点以下の部分木においての題意を満たす場合の数について数え上げれるんじゃないかという考えになりました．
そして遷移を一億年ほど考えた結果解けました
以下プログラム同様，各頂点vについて，自分を黒く塗るときの自分以下の部分木を塗る場合の数をv.black，自分を白く塗るときのそれをv.white，自分を除くときのそれをv.remとして軽く説明します．
自分を黒く塗る場合の数
各頂点から子に対して画像のような関係があり得ます．左から，
- 自分と子が繋がっていて，子を白く塗る ch.white
- 自分と子が繋がっていて，子の子はない ch.rem
- 自分と子が繋がっていて，それで終わり 1
- 自分と子が繋がっていない ch.white+ch.black+ch.rem
ここで注意なのは，左から3番目のような場合の数はch.remには含まれていないため+1を忘れずにしてあげることです．なぜならch.remにはその子を使わないような子以下の部分木で題意を満たすような集合の個数を数え上げています．ですので頂点が1つだけポツンとあるような場合は辺が1本もないため，題意を満たすような集合ではないため，別で数えてあげる必要があります．
よって，それぞれの子についてこれらの状態の場合の数の和の総積をとると自分を黒く塗るような場合の数が計算できそうです．
ところで，これだと以下のような自分だけ1個で孤立するような状態を数えてしまうので引きます
自分を白く塗る場合の数
おんなじ感じで頑張ります
自分を使わないとき
ch.black+ch.white+ch.rem+1の総積-1
ch以下を全く使わない場合を考慮して+1，一つも何も使わない空集合を後から引くから-1
おわりに
途中からわかりやすく説明するの無理じゃんとなって書く気が減退しました
