We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
sys.setrecursionlimit(100000)modulus=10**9+7# Return the number of ways that this subtree can be allocated if its root# has 1. the opposite assignment as its parent and 2. the same assignmentdefways(node,parent,edges):# children are all neighbors except the parentchildren=edges[node]ifparent:children.remove(parent)# we keep track of "lonely_ways", the number of ways that all subtree can# be assigned with opposite root assignments# (because if they're all opposite, this node must be the same as its parent)lonely_ways=1# keep track of the total number of ways: product of # of ways for subtreestotal_ways=1forchildinchildren:(diff,same)=ways(child,node,edges)lonely_ways=(lonely_ways*diff)%modulustotal_ways=(total_ways*(same+diff))%modulus# if we're different from our parent, we cannot include cases where we're# also different from all of our childrenreturn(total_ways-lonely_ways,total_ways)defkingdomDivision(n,roads):edges=dict()fora,binroads:edges.setdefault(a,set()).add(b)edges.setdefault(b,set()).add(a)# Depth-first recurssion of the tree rooted at 1 (root has None parent)(diff,same)=ways(1,None,edges)# "diff" is the now number of ways to assign the whole tree without a lonely# root, given a root of a fixed assignment.# Multiply by 2 for # of root assignmentsreturn(2*diff)%modulus
Cookie support is required to access HackerRank
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 →