Tree Matching

def solution(n, tree):
	# dp[node][0] represents max count of tree matching of tree rooted at node where u is not included in edge
	# dp[node][1] where node is included in one edge
    dp = [[0,0] for _ in range(n+1)]
 
    def dfs(u, parent):
		# Count without including u
        for v in tree[u]:
            if v == parent:
                continue
            dfs(v, u)
            dp[u][0] += max(dp[v][0], dp[v][1])
 
 
		# Count including u in one of the child with max
        for v in tree[u]:
            if v == parent:
                continue
            use_edge = 1 + dp[v][0] + (dp[u][0] - max(dp[v][0], dp[v][1]))
            dp[u][1] = max(dp[u][1], use_edge)
 
    dfs(1, -1)
    return max(dp[1][0], dp[1][1])
 
 
 
if __name__ == "__main__":
    n = int(input())
 
    from collections import defaultdict
 
    tree = defaultdict(list)
 
    for _ in range(n-1):
        a, b = tuple(map(int, input().split()))
        tree[a].append(b)
        tree[b].append(a)
 
    print(solution(n, tree))
 

Question