Fixed-Length Paths I.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, ~~Swift~~, TCL, Text, Turing, VB, Zig

Dado un árbol de $n$ ~n~ nodos, su tarea es contar el número de caminos distintos que constan de exactamente $k$ ~k~ aristas.

Entrada

La primera línea de entrada contiene dos enteros $n$ ~n~ y $k$ ~k~: el número de nodos y la longitud del camino. Los nodos están numerados $1,2,\ldots,n$ ~1,2,\ldots,n~. Luego hay $n-1$ ~n-1~ líneas que describen las aristas. Cada línea contiene dos enteros $a$ ~a~ y $b$ ~b~: hay una arista entre los nodos $a$ ~a~ y $b$ ~b~.

Salida

Imprima un entero: el número de caminos.

Restricciones

$1 \leq k \leq n \leq 2 \cdot 10^5$ ~1 \leq k \leq n \leq 2 \cdot 10^5~
$1 \leq a,b \leq n$ ~1 \leq a,b \leq n~

Ejemplo de Entrada

Ejemplo de Salida

Comments

There are no comments at the moment.