balance.py

import sys

class Balance(object):
    def __init__(self, ident):
        # Balance identifer
        self.ident = ident

        # Left/right hand weights
        self.wl = 0
        self.wr = 0

        # Left/right hand balance indices
        self.bl = list()
        self.br = list()

        # Total weight of balances on either side
        self.child_l = 0
        self.child_r = 0

        # Extra weight added to both sides (in practice only one side will have
        # weight added
        self.extra_l = 0
        self.extra_r = 0

    def get_total_weight(self):
        return self.extra_l + self.extra_r + \
            self.child_l + self.child_r + \
            self.wl + self.wr + 10

    def balance(self, balances):
        self.child_l = 0
        self.child_r = 0

        for b in self.bl:
            balances[b].balance(balances)
            self.child_l += balances[b].get_total_weight()

        for b in self.br:
            balances[b].balance(balances)
            self.child_r += balances[b].get_total_weight()

        imbalance = (self.child_l + self.wl) - (self.child_r + self.wr)
        if imbalance > 0:
            self.extra_r += imbalance
        else:
            self.extra_l += -imbalance

balances = list()
num_balances = int(sys.stdin.readline())

while num_balances > 0:
    line_l = sys.stdin.readline().split()
    line_r = sys.stdin.readline().split()

    balance = Balance(len(balances))

    balance.wl = int(line_l[0])
    balance.bl = map(int, line_l[1:])
    balance.wr = int(line_r[0])
    balance.br = map(int, line_r[1:])

    num_balances -= 1
    balances.append(balance)

# Determine the balances that are on the floor (root nodes in the forest of balance trees)
root_balances = set(range(0, len(balances)))
for balance in balances:
    root_balances -= set(balance.bl)
    root_balances -= set(balance.br)

for b in root_balances:
    balances[b].balance(balances)

for balance in balances:
    print "%d: %d %d" % (balance.ident, balance.extra_l, balance.extra_r)