Count Independent Sets in a Tree

Given an undirected tree, count the number of essentially different independent sets. An independent set of a graph is a set of vertices where no two vertices are adjacent. In this problem, you are given a tree with n nodes and n-1 edges. You need to calculate the total number of independent sets. Note that the empty set is also considered an independent set.

Note: The solution can be achieved using a DFS dynamic programming approach. For each node (u), define two values: (dp[u][1]) as the number of independent sets that include (u) and (dp[u][0]) as the number of independent sets that do not include (u). The recurrence is given by:

[ dp[u][1] = \prod_{v \in child(u)} dp[v][0], \quad dp[u][0] = \prod_{v \in child(u)} (dp[v][0] + dp[v][1]). ]
The answer is (dp[root][0] + dp[root][1]). You can choose any node as the root since the tree is undirected.

inputFormat

The first line contains an integer n representing the number of nodes in the tree. The nodes are numbered from 1 to n.

Each of the following n - 1 lines contains two integers u and v indicating that there is an edge between node u and node v.

outputFormat

Output a single integer, the number of independent sets in the tree.

sample

1

2