Path with length k - MarisaOJ: Marisa Online Judge

Given a tree of

$n$ vertices. Count the number of simple paths with length

$k$ . ### 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 paths with length

$k$ . ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le k \le 100$ . -

$1 \le u, v \le n$ . ### Example Input:

$5 2 1 2 2 3 1 4 4 5$

Output:

$3$

Topic

Graph

Tree

Dynamic Programming

Rating

1300

Solution (1)

Solution