Xor circuit codechef dp on tree

#1

why multiply the number of ways together ? (at 5:00)

#2

Since we need to find the total number of set of values that would give xor=0 from the path.
Assume this kind of a graph
A
/ \
B C
\ /
D

if there are 3 set of values for path A-B-D and 4 set of values for path A-C-D, then a total of 12 unique set are possible together.
So we multiply. It’s simple logic of counting.
I hope you get this.

1 Like