Tree Paths of Length K

Difficulty: 2000 6000 ms 128 MB

dp trees

Count the unordered pairs of nodes whose tree-path length (number of edges) is exactly K.

Input: the first line has N and K; the next N−1 lines have the edges.

Output: the number of node pairs at distance exactly K.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 500

Sample Tests

4 2
1 2
2 3
2 4

3

2 1
1 2

1

Read the Editorial