SPOJ - PT07X

spoj_pt07x.py

# http://www.spoj.com/problems/PT07X/
from functools import lru_cache
d = {}
@lru_cache(maxsize=None)
def f(u, taken, parent):
	s0, s1 = 0, 0
	for v in d[u]:
			if taken and v!=parent: s0 += min(f(v, 1, u), f(v, 0, u))
			elif v!=parent: s1 += f(v, 1, u)
	if taken: return 1 + s0
	else: return s1

n = int(input())
if n == 1: print(1) and exit(0)
for i in range(n): d[i] = []
for i in range(n - 1):
	u, v = list(map(int, input().split()))
	d[u - 1].append(v - 1); d[v - 1].append(u - 1)
print(min(f(0, 0, -1), f(0, 1, -1)))