Cosidering the states , i didn’t understand how the transition was made.Especially why both [0] and [1] was.I mean i didn’t understand it even after watching twice.Please explain in detail.
Didn't understand the transition
@nihal.striker 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]”
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.