센트로이드 분할

문제

$N$개의 정점으로 이루어진 트리가 주어진다. 트리에서 두 정점 사이의 경로에 포함된 간선의 개수를 두 정점 사이의 거리라 한다.

트리에 존재하는 모든 정점 쌍 중 거리가 정확히 $K$인 쌍의 개수를 구하라. 이때 정점의 순서만 다른 쌍 $(u, v)$와 $(v, u)$는 같은 쌍으로 세며, $(u, u)$와 같이 두 정점이 동일한 쌍도 포함하지 않는다.

센트로이드 분할(centroid decomposition) 알고리즘을 활용하여 문제를 해결하라.

입력

첫째 줄에 트리의 정점 수 $N$과 구하고자 하는 거리 $K$가 공백으로 구분되어 주어진다.
둘째 줄부터 $N-1$개의 줄에 걸쳐 간선의 정보가 주어진다. 각 줄에는 간선의 양끝 정점 번호 $u$, $v$가 공백으로 구분되어 주어진다.

제한

• $2 \le N \le 100,000$
• $1 \le K \le 10^9$
• $1 \le u, v \le N$
• 주어지는 그래프는 항상 연결된 트리 형태이며, 중복 간선이나 자기 자신을 잇는 간선은 주어지지 않는다.

출력

트리에서 거리가 정확히 $K$인 서로 다른 두 정점 쌍의 개수를 출력하라.

예제 입력 1

5 2
1 2
2 3
3 4
4 5

예제 출력 1

3

예제 입력 2

5 3
1 2
2 3
3 4
4 5

예제 출력 2

2