Cây về không

Cho một cây gồm $N$ đỉnh được đánh số từ $1$ đến $N$. Trên đỉnh thứ $i$ có ghi một số nguyên $v_i$.

Mỗi bước, bạn được thực hiện thao tác sau:

1. Chọn một cây con của cây đã cho, tức là một tập đỉnh liên thông (cùng với các cạnh nối chúng), sao cho tập đỉnh này chứa đỉnh $1$.
2. Tăng thêm $1$, hoặc giảm đi $1$, tất cả các số ghi trên những đỉnh vừa chọn.

Lưu ý rằng mỗi thao tác chỉ được cộng $1$ hoặc trừ $1$ (không được chọn lượng thay đổi lớn hơn), và tập đỉnh được chọn luôn phải liên thông và luôn phải chứa đỉnh $1$.

Hãy tìm số bước ít nhất để đưa toàn bộ các số ghi trên cây về $0$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$.
• $N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$, cho biết có một cạnh nối đỉnh $a_i$ và đỉnh $b_i$. Dữ liệu đảm bảo đồ thị cho trước là một cây.
• Dòng cuối cùng chứa $N$ số nguyên $v_1,v_2,\dots ,v_N$.

Dữ liệu ra

Một số nguyên duy nhất là số bước ít nhất cần thực hiện.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le a_i,b_i\le N$, $a_i\ne b_i$
• $|v_i|\le {10}^9$

Ví dụ