Python 代码

import sys
sys.setrecursionlimit(10000000)

def add(a, b):
    global idx
    e[idx] = b
    h[a], ne[idx] = idx, h[a]
    idx += 1

def dfs(cur, pre):
    nn = h[cur]
    r1, r2 = 0, 1
    while nn != -1:
        son = e[nn]
        if son != pre:
            s1, s2 = dfs(son, cur)
            r1 += s2
            r2 += min(s1, s2)
        nn = ne[nn]
    return r1, r2

while True:
    n = sys.stdin.readline().strip()
    if not n: break
    n = int(n)
    idx = 0
    h, e, ne = [-1] * (n+1), [0] * (2*n+1), [0] * (2*n+1)
    for _ in range(n):
        char = input().split(':')
        a = int(char[0])
        bs = list(map(int, char[1].split(')')[1].strip().split()))
        for b in bs:
            add(a, b)
            add(b, a)
    r1, r2 = dfs(0, -1)
    print(min(r1, r2))