2色のツリーに彩色する

Question

私はツリーを持っていて、各ノードに色付けしたいと思っていますblack or white。ツリー着色有効であると言われている場合
For every node N there exist at least One neighbor with the same color as of N

私のアプローチ：は
はDPを構築しましょう[2] 0,1は黒と白の

ways = (dp[0][i1]+dp[1][i1])*(dp[0][i2]+dp[1][i2)*.....i upto All Children of N 

    dp[0][N] = (ways-Number of ways when all the children are 1) 
    dp[1][N] = (ways-Number of ways when all the children are 0) 

しかし、私のアプローチを表す[N]私に正解を与えていないのですか？私が逃しているものを手伝ってください。各ノードuについて

Answer 1

、C(u)はuをルートとするサブツリーの有効な着色剤の数であり、そしてA(u)はuの全て適切な子孫が同じ着色隣人（「ほとんど有効」）を有している着色剤の数としてみましょう。再発は

C(u) = A(u) - 2 product_{v is a child of u} (C(v)/2) 
A(u) = 2 product_{v is a child of u} (C(v)/2 + A(v)/2) 

A(u)ためのロジックは、（1）2つの色が（3）それぞれの子vがu同じ着色ルート（2）が有効でなければならない異なるuからv着色各子供のために存在することですほとんど有効でなければなりません。 C(u)の論理は、すべての子供がその親と異なる可能性のある着色がほとんど有効であるということです。