📘 Mô tả

Cho một cây có n đỉnh đánh số từ 1 đến n. Với mỗi đỉnh i bạn được chọn một giá trị nguyên ai sao cho li ≤ ai ≤ ri. Độ đẹp của cây được định nghĩa là tổng |au - av| trên mọi cạnh (u, v). Hãy tìm giá trị độ đẹp lớn nhất có thể.

📥 Input

• Dòng đầu chứa số nguyên n.
• n dòng tiếp theo, mỗi dòng gồm hai số nguyên li, ri.
• n - 1 dòng cuối, mỗi dòng gồm hai số nguyên u, v mô tả cạnh nối u với v.

📤 Output

In ra giá trị độ đẹp lớn nhất của cây.

🔒 Ràng buộc

• 1 ≤ n ≤ 105
• 1 ≤ li ≤ ri ≤ 109
• 1 ≤ u, v ≤ n

🧪 Ví dụ

Input:

3
1 3
4 6
7 9
1 2
2 3

Output:

8