Bài tập này được chấm theo batch.

Đêm nay lại là một đêm cô đơn với Gấu. Vào cái ngày mà đáng lẽ anh ấy phải cùng người thương, người thân, bạn bè đi chơi lễ hội Halloween, tham gia các cuộc vui,... thì anh ta lại phải cô đơn trong nhà và làm bài toán sau:

Cho một cây ~n~ đỉnh, các cạnh được đánh số từ ~1~ đến ~n-1~, và một số nguyên dương ~k~, Gấu định nghĩa một hàm ~f(l, r)~ như sau:

• Không sử dụng các cạnh có chỉ số từ ~l~ đến ~r~. Lúc này, ~n~ đỉnh và các cạnh còn lại tạo thành sẽ là một rừng cây, giả sử rừng gồm ~\nu~ cây đánh số ~T_1, T_2, \dots, T_\nu~.
• Gấu sử dụng ~\nu-1~ cạnh để nối ~\nu~ cây trong rừng lại với nhau sao cho sau ~\nu-1~ phép nối cạnh, thì rừng chỉ còn đúng một cây gồm ~n~ đỉnh và ~n-1~ cạnh.
• Gọi ~d~ là khoảng cách xa nhất giữa hai đỉnh ~u, v~ bất kỳ sau khi nối ~\nu-1~ cạnh. Nếu tồn tại một cách nối sao cho ~d \leq k~ thì ~f(l, r) = 1~, ngược lại ~f(l, r) = 0~.

Hãy tính tổng ~f(l, r)~ với mọi ~1 \leq l \leq r \leq n - 1~.

Nhắc lại:

• Cây là một đồ thị vô hướng liên thông và không có chu trình.
• Một rừng cây là một tập hợp gồm các cây.
• Khoảng cách giữa hai đỉnh trên cây là số cạnh trên đường đi đơn giữa hai đỉnh ấy.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên ~n, k~ ~(1 \leq n, k \leq 200000)~.
• ~n-1~ dòng sau, mỗi dòng gồm hai số nguyên ~u, v~ mô tả một cạnh của cây ~(1 \leq u, v \leq n)~.

Dữ liệu ra

Gồm một số nguyên không âm là đáp án bài toán.

Tính điểm

• Subtask $1$ ($2$ điểm): $1 \leq n \leq 2$.
• Subtask $2$ ($14$ điểm): $1 \leq n \leq 200$.
• Subtask $3$ ($26$ điểm): $1 \leq n \leq 2000$.
• Subtask $4$ ($16$ điểm): Các cạnh của cây có dạng $(i, i+1)$ với $1 \leq i < n$.
• Subtask $5$ ($42$ điểm): $1 \leq n \leq 200000$.

Ví dụ

Đầu vào

7 3
1 2
2 4
3 5
4 6
1 5
4 7

Đầu ra

13

Giải thích

Đồ thị có dạng như hình phía dưới, cạnh $(u, v, i)$ thể hiện cạnh $u, v$ trên cây có chỉ số $i$

Các cặp ~(l, r)~ mà ~f(l, r) = 1~ là:

• ~(1, 1); (1, 2); (1, 3); (1, 4); (1, 5); (1, 6)~
• ~(2, 3); (2, 4); (2, 5); (2, 6)~.
• ~(3, 5); (3, 6)~.
• ~(4, 6)~.

Ví dụ:

• ~l = 1, r = 2 \rightarrow~ Đồ thị là một rừng với ~3~ cây:
  • ~T_1~: gồm các đỉnh ~1, 5, 3~.
  • ~T_2~: gồm đỉnh ~2~.
  • ~T_3~: gồm các đỉnh ~4, 6, 7~.
  • Gấu thực hiện nối đỉnh ~4~ của cây ~T_3~ và đỉnh ~2~ của cây ~T_2~ vào đỉnh ~5~ của cây ~T_1~. Lúc này khoảng cách xa nhất là từ ~1~ đến ~6~, do đó ~d = 3 \leq k = 5~.

• ~l = 2, r = 4 \rightarrow~ Đồ thị là một rừng với ~4~ cây:
  • ~T_1~: gồm các đỉnh ~1, 2, 5~.
  • ~T_2~: gồm các đỉnh ~4, 7~.
  • ~T_3~: gồm đỉnh ~3~.
  • ~T_4~: gồm đỉnh ~6~.
  • Gấu thực hiện nối đỉnh ~4~ của cây ~T_2~, đỉnh ~3~ của cây ~T_3~ và ~6~ của cây ~T_4~ vào đỉnh ~1~ của cây ~T_1~. Lúc này khoảng cách xa nhất là từ ~5~ đến ~7~, do đó ~d = 3 \leq k = 5~.