Cho cây \(n\) đỉnh. Đỉnh \(i\) có giá trị đỏ \(c_i\) và xanh \(p_i\). Với mỗi truy vấn đường đi ngắn nhất từ \(A\) đến \(B\), duyệt các đỉnh trên đường theo thứ tự và chọn đỏ hoặc xanh cho từng đỉnh.

Một tiền tố của đường đi là hài hòa nếu số lần chọn một màu không nhiều hơn màu còn lại ít nhất ba lần. Mọi thời điểm trong quá trình chọn màu phải hài hòa. Giá trị của đường đi là tổng giá trị theo các màu đã chọn. Hãy tìm giá trị lớn nhất của một cách tô hài hòa cho mỗi truy vấn.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n,q\le10^5\)). Dòng hai chứa \(c_i\) và dòng ba chứa \(p_i\) (\(-10^9\le c_i,p_i\le10^9\)). \(n-1\) dòng tiếp theo là các cạnh cây. \(q\) dòng cuối chứa \(u,v\) của các truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in giá trị lớn nhất của cách tô hài hòa trên một dòng.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(27\) điểm: \(n,q\le15\).
2. \(41\) điểm: \(n,q\le1000\).
3. \(19\) điểm: \(q\le10000\).
4. \(23\) điểm: không có ràng buộc thêm.

Ví dụ

4 1
10 10 10 10
-10 0 -10 0
1 2
2 3
3 4
1 4

30

5 3
-5 -4 0 -3 3
3 1 -5 0 0
3 2
1 4
3 5
1 2
2 5
5 3

4
3
3

Nguồn

COCI 2025/2026 - Vòng 1, bài Harmonija.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.