You are viewing a single comment's thread. Return to all comments →
You may try the following approach if you didn't get the editorial. Observe that if you know that answers (valid combinations) for the children of a node, you can calculate the answer for that node from the answers of it's children. - This can be done as following: Suppose a node has N children. If the child C1 is given color red (0), suppose number of valid combinations for that configuration (with child C1 as red) are C1r. If the child C1 is given color black (1), suppose number of valid combinations for that configuration (with child C1 as black) are C1b. Similarly the answer for ith child with color as red is Cir and with color as black is Cib. Then the answer for that parent node should be (C1r+C1b)*(C2r+C2b)*.........(CNr+CNb). This may seem right at the first glance but it's not always true, as we MAY have also added some invalid combinations while we calculated our answer for the parent node. What are these invalid combinations? Suppose the parent has color black, then we've also added the combinations in our answer for the parent node where C1 is red, C2 is red,.... CN is red, which are (C1r*C2r*C3r....CNr). BUT POINT 1 - These combinations are only invalid, if the parent's color is black and the color of parent's parent is red (as these combinations clearly leaves the parent(black) with no other black nodes directly connected to it, which are indeed invalid as the children with red color can then attack it's parent with black color) POINT 2 - Same combinations are valid, if the parent's color is black and the color of parent's parent is also black. So we have to maintain two things. What's the color of current node? Is the color of current node's parent same as the color of current node (which I've done as 2, if true, and 1 if false in my code)? So, if the color of node and node's parent are same, then don't subtract the 'potential' invalid combinations, else subtract them. Recursively calculate answer for each node using DFS. Memoise for 10^5. You may check out the this code https://pastebin.com/k1bs4uRQ .
Seems like cookies are disabled on this browser, please enable them to open this website
Kingdom Division
You are viewing a single comment's thread. Return to all comments →