Informática Intermediário - Semana 73

Distâncias na Árvore

Uma árvore é um grafo conexo que não possui nenhum ciclo. A distância entre dois vértices de uma árvore é o tamanho (em arestas) da menor distância entre esses nós.

Você tem uma árvore com n vértices e um inteiro positivo k. Encontre o número de pares distintos de vértices que possuem uma distancia de exatamente k arestas entre si. Note que os pares (v, u) e (u, v) representam o mesmo par.

Entrada

A primeira linha contem dois inteiros n e k (1 \leq n \leq 50000, 1 \leq k \leq 500), respectivamente, o número de vértices e a distância requirida entre os vértices. Cada uma das próximas n - 1 contém dois inteiros u e v que representam uma aresta entre os vértices u e v. Todas as arestas são distintas.

Saída

Imprima um único inteiro, o número de pares distintos de vértices que possuem uma distância k entre si.

Não use %lld como especificador para a leitura ou escrita de inteiros 64-bit em C++. É preferível usar os streams cin, cout ou o especificador %I64d.

Exemplos

ENTRADA SAÍDA
5 2

1 2

2 3

3 4

2 5

4
ENTRADA SAÍDA
5 3

1 2

2 3

3 4

4 5

2

Enviar solução: codeforces