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

Enviar solução: codeforces