Tree construction

3.2

5 votes
Graphs, Algorithms, Breadth-first search
Problem

You are given a tree consisting of $$n$$ nodes.

You can select any number of nodes from the tree that you want to save. The remaining nodes will be destroyed but the saved nodes again form a tree.

Find the total number of such ways to form the tree.

Note: You may not select any node or you may save all nodes.

Input format

  • The first line contains a single integer $$N$$ ( 2 ≤ $$N$$ ≤ $$10^5$$) denoting the number of nodes in the tree.
  • Next $$N-1$$ lines contain two integers, $$u$$ and $$v$$, denoting an edge from node $$u$$ to node $$v$$ ($$0 \le u,v < N$$).

Output format

Print the required number of ways modulo $$10^9 + 7$$.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

You has these options {},{0},{1},{2},{0,1},{1,2},{0,2}, {0,1,2}. Out of these, only 7 are valid trees as {0,2} does not form a single tree.

Editor Image

?