\text{Đường đi tổng K}

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Khu rừng FPTOJ có \(N\) cây và \(N-1\) con đường, mỗi con đường có độ dài \(w_i\). Tèo muốn đếm xem có bao nhiêu đường đi đơn (không lặp đỉnh) giữa hai cây bất kỳ mà tổng độ dài đúng bằng \(K\).

Yêu cầu: Đếm số đường đi có tổng trọng số bằng \(K\).

Đầu vào

• Dòng đầu tiên chứa hai số nguyên \(N, K\) (\(1 \le N \le 2 \times 10^5\), \(1 \le K \le 10^6\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa \(u, v, w\) (\(1 \le w \le 10^6\)).

Đầu ra

• In ra số đường đi có tổng trọng số bằng \(K\). Nếu không có đường đi nào, in ra \(-1\).

Ví dụ

Đầu vào:

5 4
1 2 3
2 3 1
2 4 2
4 5 2

Đầu ra:

2

Giải thích

Đường đi \(1\to2\to3\) có tổng \(3+1=4\). Đường đi \(5\to4\to2\to3\) có tổng \(2+2+1=5\) (không). Đường đi \(5\to4\to2\to1\) có tổng \(2+2+3=7\) (không). Đường đi \(3\to2\to4\to5\) có tổng \(1+2+2=5\) (không). Đường đi \(4\to2\to3\) có tổng \(2+1=3\) (không). Chỉ có 1 đường đi tổng 4: 1→2→3 = 3+1=4. Còn đường 3→2→1 = 1+3=4 là giống. Vậy chỉ 1. Output 2? Có thể 3→2→1 và 1→2→3 được tính là 2... hoặc còn đường 5→4→2→? 5-4=2, 4-2=2, tổng 4 rồi dừng! Đường đi 5→4 có tổng 2 (sai). Đường 5→4→2 có tổng 2+2=4 - đúng! Vậy có 2 đường: 1→2→3 (3+1=4) và 5→4→2 (2+2=4). Mỗi đường được tính 1 lần. Answer = 2.

Subtask