Окраска дерева двумя цветами

Question

У меня есть дерево, и я хочу покрасить каждый узел black or white. Дерево считается действительным, если цвета
For every node N there exist at least One neighbor with the same color as of N

Мой подход:
позволяют построить дп [2] [N], где 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) 

Но мой подход не дает мне правильного ответа? Пожалуйста, помогите мне, что мне не хватает?

Answer 1

Для каждого узла u, пусть 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) каждый ребенок v цвета в отличие от u должен быть действительным (3) каждый ребенок v цветной такой же, как u должно быть почти справедливо. Логика для C(u) заключается в том, что возможные раскраски, в которых все дети отличаются от родителя, являются почти допустимыми.