[tree] k Path

Cho một đồ thị dạng cây n đỉnh, các cạnh được biểu diễn bằng ma trận 2 chiều edges. Bạn hãy viết hàm đếm số cặp (u, v) khác nhau sao cho độ dài ngắn khi đi từ đỉnh u tới đỉnh v đúng bằng k.

Lưu ý: Cặp (u, v) và (v, u) được coi là giống nhau.

Ví dụ:

• Cho n = 4, edges = [[1, 2], [2, 3], [3, 4]], k = 2, output là kPath(n, edges, k) = 4.
  Giải thích:
  
  
  Có 4 cặp (u, v) có độ dài đường đi ngắn nhất là 2: (1, 4), (1, 4), (2, 5), (4, 3).
• Cho n = 4, edges = [[1, 2], [2, 3], [3, 4], [4, 5]], k = 3, output là kPath(n, edges, k) = 2.
  Giải thích:
  
  
  Có 2 cặp (u, v) thỏa mãn yêu cầu là: (1, 4), (2, 5).

Đầu vào/Đầu ra

• [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, JS và Go

• [Đầu vào] Integer n
  1 <= n <= 1000

• [Đầu vào] Matrix of integer edges.
  edges.size = n - 1
1 <= edges[i][j] <= n

• [Đầu vào] Integer k
  1 <= k <= 100

• [Đầu ra] Integer