29 lines
562 B
Python
29 lines
562 B
Python
import sys
|
|
sys.setrecursionlimit(10**6)
|
|
input = sys.stdin.readline
|
|
|
|
N = int(input())
|
|
graph = [[] for _ in range(N+1)]
|
|
|
|
for _ in range(N-1) :
|
|
u, v = map(int, input().split())
|
|
graph[u].append(v)
|
|
graph[v].append(u)
|
|
|
|
dp = [[0]*2 for _ in range(N+1)]
|
|
visited = [False] * (N+1)
|
|
|
|
def dfs(n) :
|
|
visited[n] = True
|
|
dp[n][0] = 1
|
|
|
|
for nxt in graph[n] :
|
|
if visited[nxt] :
|
|
continue
|
|
|
|
dfs(nxt)
|
|
dp[n][0] += min(dp[nxt][0], dp[nxt][1])
|
|
dp[n][1] += dp[nxt][0]
|
|
|
|
dfs(1)
|
|
print(min(dp[1][0], dp[1][1])) |