Maximum Independent Set in a Tree

You are given a tree with N nodes and N-1 edges. A tree is an acyclic connected graph. Your task is to find the maximum number of nodes that can be chosen such that no two chosen nodes are directly connected by an edge. In other words, you need to compute the size of the maximum independent set of the tree.

An independent set \(S\) in a graph \(G=(V,E)\) is a subset of vertices \(S \subseteq V\) such that for every edge \((u,v) \in E\), at most one of \(u\) and \(v\) is in \(S\).

Input: The input begins with an integer N representing the number of nodes in the tree. Then follow N-1 lines, each containing two integers \(u\) and \(v\) representing an undirected edge between nodes \(u\) and \(v\).

Output: Output a single integer denoting the size of the maximum independent set of the tree.

Note: You must read input from stdin and print the output to stdout.

inputFormat

The first line contains an integer N (\(1 \leq N \leq 10^5\)), the number of nodes in the tree. The next N-1 lines each contain two integers \(u\) and \(v\) (\(1 \leq u,v \leq N\)), representing an edge between nodes \(u\) and \(v\).

You can assume that the given graph is always a tree.

outputFormat

Output a single integer which is the maximum number of nodes that can be chosen such that no two chosen nodes are adjacent.

5
1 2
1 3
3 4
3 5

3