Alex y su árbol


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Alex tiene un árbol (grafo conexo sin ciclos) de n vértices, con todas las aristas con peso igual a 1 unidad. La distancia entre dos vértices de un árbol es la suma de los pesos de las aristas que están en el único camino entre estos vértices.

Alex quiere que le ayudes a determinar la cantidad de pares de vértices tal que cumplan que estén a una distancia de exactamente k unidades. Note que los pares (u,v) y (v,u) son considerados el mismo par.

Entrada

La primera línea contiene los enteros n y k (1<=n<=50000;1<=k<=500). Las siguientes n-1 líneas son las aristas del árbol de la forma ai, bi (1<=ai,bi<=n). Se garantiza que estas aristas formen un árbol.

Salida

Imprima en una única línea la respuesta del problema.

Ejemplo de Entrada #1

5 2
1 2
2 3
3 4
2 5

Ejemplo de Salida #1

4

Ejemplo de Entrada #2

5 3
1 2
2 3
3 4
4 5

Ejemplo de Salida #2

2

Explicación del primer ejemplo: Los pares son (1,3);(1,5);(3,5) y (2,4).


Comments

There are no comments at the moment.