Subgraph - MarisaOJ: Marisa Online Judge

HOME
PROBLEMSET
ROADMAP
COMPETITION
TOPIC
RANKING
GUIDE
MASHUP
ABOUT
CONTACT

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$

DP on tree
	Tree coloring
	Tree coloring 2
	Maximum sum path
	Path with length k
	Subgraph
	Beautiful tree
	Company
	Zero tree
	Selfie

Topic

Graph

Tree

Dynamic Programming

Rating

1300

Solution (1)

Solution