Mô tả và yêu cầu

TRẠM THU PHÁT SÓNG

Mạng lưới liên lạc giữa N trạm phát sóng có dạng một cái cây (đồ thị vô hướng,
liên thông, không có chu trình). Trung tâm điều hành cần biết khoảng cách
ngắn nhất giữa hai trạm u và v bất kỳ để tối ưu hóa tín hiệu.

Dữ liệu vào

* Dòng 1: N và Q (N,Q≤105).

* N−1 dòng tiếp theo: Các cạnh của cây kèm trọng số w.

* Q dòng tiếp theo: Mỗi dòng gồm 2 số u,v.

Kết quả: In ra khoảng cách giữa u và v cho mỗi câu hỏi.

Ví dụ

INPUT                         OUTPUT
                   6 3                           6
                   1 2 3                         11
                   1 3 5                         7
                   2 4 2
                   2 5 4
                   3 6 1
                   4 5
                   4 6
                   1 5