Cho một cây có \(n\) nút. Tại mỗi nút \(i\) có ghi một số nguyên \(a_i\). Mỗi thao tác bạn được chọn một nút và lấy số ghi trong nút đó tăng lên hoặc giảm đi \(1\) đơn vị. Bạn hãy chuyển cây về trạng thái thỏa mãn:

• Tại mỗi nút lá giá trị bằng \(0\) hoặc \(1\),
• Giá trị tại mỗi nút cha bằng tổng giá trị của các nút con.

Input

• Dòng đầu chứa số \(n\) \((1 \leq n \leq 10^5)\)
• Dòng thứ hai chứa \(n\) số \(a_1, a_2, ..., a_n\) \((0 \leq a_i \leq 10^5)\)
• \(n-1\) dòng tiếp theo mỗi dòng ghi hai số \(x, y\) cho biết hai nút \(x, y\) có quan hệ cha-con. Nút \(1\) luôn là gốc của cây.
• Các số trên một dòng của input file được ghi cách nhau bởi dấu cách

Output

• Ghi ra một số nguyên duy nhất là số thao tác ít nhất tìm được.

Example

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

4