Tối ưu hóa độ trễ

Một nhà cung cấp dịch vụ Internet vận hành một mạng lưới gồm N trạm, được nối với nhau bằng N - 1 tuyến cáp quang tạo thành một cấu trúc cây. Mỗi tuyến cáp nối hai trạm U và V có độ trễ là W. Độ trễ truyền thông giữa hai trạm bất kỳ là tổng độ trễ trên đường đi đơn giữa chúng. Độ trễ của mạng được định nghĩa là độ trễ truyền thông lớn nhất giữa tất cả các cặp trạm.

Để nâng cao chất lượng dịch vụ, nhà cung cấp đề xuất Q phương án nâng cấp. Mỗi phương án gồm việc thay thế các trạm trên một đường đi cụ thể bằng một trạm mới duy nhất. Cụ thể, ở phương án thứ i (1 <= i <= Q), hai trạm Ai và Bi được chọn. Toàn bộ các trạm trên đường đi đơn giữa Ai và Bi sẽ được gộp lại thành một trạm mới. Mọi tuyến cáp bên ngoài nối tới các trạm được gộp này sẽ được kết nối lại với trạm mới và giữ nguyên độ trễ ban đầu.

Nhà cung cấp cần tính toán độ trễ mạng thu được cho từng phương án đề xuất. Lưu ý rằng các phương án này chỉ mang tính giả định và được đánh giá độc lập với nhau mà không thực sự làm thay đổi mạng lưới.

Đầu vào:

• Dòng đầu tiên chứa số nguyên T là số lượng bộ test.
• Mỗi bộ test được mô tả như sau:
  • Dòng đầu tiên chứa số nguyên N (1 <= N <= 10^5).
  • N - 1 dòng tiếp theo, mỗi dòng chứa ba số nguyên U, V, W (1 <= U, V <= N; 1 <= W <= 10^9) mô tả một tuyến cáp.
  • Dòng tiếp theo chứa số nguyên Q (1 <= Q <= 5×10^4).
  • Q dòng tiếp theo, mỗi dòng chứa hai số nguyên Ai, Bi (1 <= Ai, Bi <= N) mô tả một phương án.
• Tổng của N trên tất cả các bộ test không vượt quá 10^5, tổng của Q trên tất cả các bộ test không vượt quá 5×10^4.

Đầu ra:

• Với mỗi phương án, in ra một số nguyên trên một dòng biểu thị độ trễ của mạng nếu áp dụng phương án đó.

Ví dụ 1:

Đầu vào:

1
10
1 2 394623
2 3 550845
3 4 167710
2 5 998205
4 6 588546
6 7 439669
1 8 565439
3 9 25600
2 10 508844
10
9 2
4 4
3 7
2 7
1 9
4 9
7 4
10 9
2 8
4 1

Đầu ra:

2194130
2744975
1958267
1958267
2194130
2577265
1958267
2194130
2744975
2026420

Ràng buộc:

• 1 <= N <= 10^5, 1 <= Q <= 5×10^4
• 1 <= U, V, Ai, Bi <= N
• 1 <= W <= 10^9
• Tổng của N trên tất cả các bộ test không vượt quá 10^5, tổng của Q trên tất cả các bộ test không vượt quá 5×10^4.