Subgraph - MarisaOJ: Marisa Online Judge

Subgraph

Time limit: 1000 ms
Memory limit: 256 MB
Given a tree with $n$ vertices, count the number of non-empty subgraphs. A subgraph is a subset of vertices that are connected by edges in the tree. ### Input - The first line contains an integer $n$. - The next $n - 1$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$. ### Output - Print the number of subgraphs, modulo $10^9+7$. ### Constraints - $1 \le n \le 10^5$. - $1 \le u, v \le n$. ### Example Input: ``` 5 1 2 1 3 3 4 3 5 ``` Output: ``` 17 ```