백준 2533 - 사회망 서비스(SNS) (파이썬)

부모가 얼리어답터면 자식은 얼리어답터여도 아니여도 됩니다.
하지만 부모가 얼리어답터가 아니라면 자식은 무조건 얼리어답터여야 합니다.

import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

dp = [[0, 0] for _ in range(n + 1)]

def dfs(num):
    visited[num] = True
    dp[num][0] = 0
    dp[num][1] = 1
    
    for i in graph[num]:
        if not visited[i]:
            dfs(i)
            dp[num][0] += dp[i][1]
            dp[num][1] += min(dp[i][0], dp[i][1])

dfs(1)
print(min(dp[1][0], dp[1][1]))