Dp formula of appleman and tree

#1

I am not able to digest the dp formula explained by sanyam bhaiya for appleman and tree problem. Can anyone help me, please.

#2

Hey @Jumbocoderzz
Sure I’ll be happy to help you
What resource should I provide you with for this issue please let me know

#3

Any other resource where i can clearly understand it…

#4

i am not able to understand, how dp[node][0] or dp[node][1] formulate?

#5

you can help me in written format (like editorials). Not whole editorial, just the formulation part( like how he formulate for black node, dp[node][1]=sum(dp[it][0]+dp[it][1])). Or if you are comfortable with video call, i am also ready for that. Thanks.

#6

@Jumbocoderzz
Please go through this once first


Then we can discuss it if you cant understand it as well

#7

@Aarnav-Jindal-1059677350830863
This blog also gives the same confusion.
for black node,
dp[node][1]=dp[node][1] * (dp[it][1] + dp[it][0])
it means we consider all possible ways such that our current node subtree form a subtree with exactly one black node.

Now my confusion is,
at last, we directly return dp[root][1] as our answer. According to this formula, we are also considering a case in which, if we attach the black node with no black group of first child then we will not attach anything with no black group of a second child. But this case is invalid according to my understanding of the question. According to question, we split tree into sets and every set must have exactly one black vertex. and we return the count of ways of such sets.

for example,
a
b c d
now we want to make answer for node ‘a’, where ‘a’ is black node and b,c,d are child of ‘a’.
If we attach node a with b’s any zero group, then c’s zero group will have not any black vertex. So this is invalid. But we are considering.

#8

@Jumbocoderzz
dp[node][1]=dp[node][1] * (dp[it][1] + dp[it][0])
This formula is incorrect and not written anywhere in the editorial buddy
Maybe you misunderstood the formula
Please see it again

#9

According to blog,
one=onedp[0][v] (considering black root we attach this root to all possible subtrees with 0 black nodes)
+ onedp[1][v] (considering black root we keep it disjoint)
+ zero*dp[1][v] (considering a white root we attach it to all the subtrees with 1 black vertex)

as I said for black node,
for black node zero always equals to 0, so
one=one*(dp[0][v]+dp[1][v]) is similar to
dp[node][1]=dp[node][1] * (dp[it][1] + dp[it][0]).

i wrote dp[node][1]=… because sanyam bhaiya wrote like this. I guess both are same. If i am incorrect, please correct me.

#10

@Aarnav-Jindal-1059677350830863
According to blog,
one=onedp[0][v] (considering black root we attach this root to all possible subtrees with 0 black nodes)
+ onedp[1][v] (considering black root we keep it disjoint)
+ zero*dp[1][v] (considering a white root we attach it to all the subtrees with 1 black vertex)

as I said for black node,
for black node zero always equals to 0(initial condition), so
one=one*(dp[0][v]+dp[1][v]) is similar to
dp[node][1]=dp[node][1] * (dp[it][1] + dp[it][0]).

i wrote dp[node][1]=… because sanyam bhaiya wrote like this. I guess both are same. If i am incorrect, please correct me.

#11

@Jumbocoderzz
Yes you’re right about the formula
Thanks for explaining
But the argument that you’re giving won’t work against the formula
For the a,b,c,d example you gave try to write the result for 0 and 1 at each node
You’ll realise that if there is no black node to which a white node is connected there’s only one way for a white node to exist which is connecting to a black node somewhere upwards

#12

if there is no black node to which a white node is connected. Then how set of no black node will connect with black node which is upwards because the connection between the set of no black node and any upwards node is that black node which is already used to make set with his another child?
Like in example of a,b,c,d
if a will go in the b’s set of no black node. then how c’s set of no black node will connect with his upwards parents because his immediate parent is used with b’s set of no black node?
bhaiya, is my question clear?

#13

@Jumbocoderzz
I hope you do understand that if a is black node
b,c,d are white lets say
So b,c,d can all connect to the same black node
In the set of nodes connected set of nodes should have a black node
There can be any number of branches of white nodes connected to this black node