백준 2533 사회망 서비스(SNS)

답

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n = int(input())
tree = [[] for _ in range(n + 1)]
dp = [[0, 0] for _ in range(n + 1)]
visited = [0] * (n + 1)

for _ in range(n - 1):
    a, b = list(map(int, input().rstrip().split()))
    tree[a].append(b)
    tree[b].append(a)

def dfs(node):
    visited[node] = 1
    dp[node][0] = 1
    for t in tree[node]:
        if not visited[t]:
            dfs(t)
            dp[node][0] += min(dp[t][0], dp[t][1])
            dp[node][1] += dp[t][0]

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

감이 안잡혀서 검색해보니 DP라는 것을 알았다ㅠㅠ
트리 구조에서 이런식으로 바텀업을 할 수 있다는 것을 알았다.
이제 안틀릴듯