Vẻ Đẹp Của Cây

Cho một cây gồm $n$ đỉnh được đánh số từ $1$ đến $n$. Mỗi đỉnh $v$ đi kèm hai số nguyên $l_v$ và $r_v$.

Bạn cần gán cho mỗi đỉnh $v$ một số nguyên $a_v$ sao cho $l_v\le a_v\le r_v$. Độ đẹp của cách gán là tổng

$$\sum _{(u,v)\in E}|a_u-a_v|$$

lấy trên tất cả các cạnh $(u,v)$ của cây.

Hãy tìm độ đẹp lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ là số đỉnh của cây.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$.
  • $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ cho biết có một cạnh nối đỉnh $u$ và đỉnh $v$. Dữ liệu đảm bảo các cạnh này tạo thành một cây.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa độ đẹp lớn nhất.

Ràng buộc

• $1\le t\le 250$
• $2\le n\le {10}^5$
• $1\le l_i\le r_i\le {10}^9$
• $1\le u,v\le n$, $u\ne v$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$

Ví dụ