I want to know better about about formula?

#1

How formula came and what is approach to get it??

#2

@ssanjuchandra hey ,
Fill a DP table such as the following bottom-up:

DP[v][0] = the number of ways that the subtree rooted at vertex v has no black vertex.
DP[v][1] = the number of ways that the subtree rooted at vertex v has one black vertex.
The recursion pseudo code is folloing:

DFS(v):
DP[v][0] = 1
DP[v][1] = 0
foreach u : the children of vertex v
DFS(u)
DP[v][1] *= DP[u][0]
DP[v][1] += DP[v][0]*DP[u][1]
DP[v][0] *= DP[u][0]
if x[v] == 1:
DP[v][1] = DP[v][0]
else:
DP[v][0] += DP[v][1]
The answer is DP[root][1].

UPD:
The above code calculate the DP table while regarding that the vertex v is white (x[v]==0) in the foreach loop.

After that the code thinks about the color of vertex v and whether we cut the edge connecting vertex v and its parent or not in “if x[v] == 1: DP[v][1] = DP[v][0] else: DP[v][0] += DP[v][1]”.
Try to dry run this code and fill dp you will get it.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.