goy division | Python Fiddle

#!/bin/python

import sys

tree = {} #structure is node: [parent-node, [child_nodes]]
has_children = set([])
nodes = []
n = int(raw_input().strip())
already_solved = {}
mod = 1000000007

for a0 in xrange(n-1):
    u,v = raw_input().strip().split(' ')
    u,v = [int(u),int(v)]
    if a0 == 0:
        root = u #arbitrary root of tree
        tree[u]=[0,[v]]
        tree[v]=[u,[]] #v is initially a leaf node
        has_children.add(u)
    else:
        nodes.append((u,v))
nodes.sort()
#build tree
for i in range(len(nodes)):
    u,v = nodes[i]
    if u in tree and v in tree:
        if tree[u][0] == -1 and tree[v][0] == -1:
            tree[u][1] = tree[u][1] + [v]
            tree[v][1] = tree[v][1] + [u]
        elif tree[u][0] == -1:
            tree[u][0] = v
            tree[v][1] = tree[v][1] + [u]
        else:
            tree[v][0] = u
            tree[u][1] = tree[u][1] + [v]
    elif u in tree:
        if tree[u][0] != -1:
            tree[u][1] = tree[u][1] + [v]
            tree[v] = [u,[]]
            has_children.add(u)
        else:
            tree[v] = [-1,[u]]
            tree[u][1] = tree[u][1] + [v]
            
    elif v in tree:
        if tree[v][0] != -1:
            tree[v][1] = tree[v][1] + [u]
            tree[u] = [v,[]]
            has_children.add(v)
        else:
            tree[u] = [-1,[v]]
            tree[v][1] = tree[v][1] + [u]
    else:
        tree[u] = [-1,[v]]
        tree[v] = [-1,[u]]
def fix_tree(node):
    if tree[node][1]:
        has_children.add(node)
    for n in tree[node][1]:
        if tree[n][0] == -1:
            tree[n][0] = node
        if node in tree[n][1]:
            tree[n][1].pop(tree[n][1].index(node))
        fix_tree(n)
fix_tree(root)
def get_ways(node):
    if node in already_solved:
        return already_solved[node]
    if node not in has_children:
        return 0
    res = 1
    if all(map(lambda x: x not in has_children, tree[node][1])):
        return 2
    else:
        num_children = 0
        children_ways = 1
        for n in tree[node][1]:
            num_children = num_children + 1
            grandchildren_ways = 0
            if tree[n][1]:
                grandchildren_ways = 1
            for g in tree[n][1]:
                grandchildren_ways = grandchildren_ways * get_ways(g) / 2
            cw = get_ways(n)
            res = res * max(1,cw + grandchildren_ways)
            children_ways = children_ways * cw
        if all(map(lambda x: x in has_children, tree[node][1])):
            pow2 = 2**(num_children)
            if node not in already_solved:
                already_solved[node] = 2*int((pow2-1)/1.0/pow2 * children_ways) + 2*(res - children_ways) 
            return 2*int((pow2-1)/1.0/pow2 * children_ways) + 2*(res - children_ways) 
        else:
            if node not in already_solved:
                already_solved[node] = 2 * res % mod
            return 2 * res
print get_ways(root)

Python Fiddle

Python Cloud IDE