Cho một cây nhị phân với ~n~ nút (đánh số từ ~1~ đến ~n~). Mỗi nút có một giá trị nguyên ~A_i~. Một cây được gọi là "cân bằng" nếu:

1. Cân bằng cấu trúc: Với mỗi nút, độ chênh lệch chiều cao giữa cây con trái và cây con phải không quá ~1~.
2. Cân bằng giá trị: Với mỗi nút, tổng giá trị của cây con trái và cây con phải phải bằng nhau.

Bạn cần tìm số lượng cây con (subtree) cân bằng trong cây đã cho.

Note: Giả sử Input chỉ có một Testcase duy nhất.

Input Specification

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(1 \le A_i \le 10^9)~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~, ~v~ ~(1 \le u, v \le n)~ biểu thị một cạnh nối giữa nút ~u~ và nút ~v~.

Output Specification

• In ra một số nguyên duy nhất: số lượng cây con cân bằng.

Constrains

• ~1 \le n \le 10^5~.
• ~1 \le A_i \le 10^9~.
• Cây đã cho là cây nhị phân hợp lệ.
• Các cạnh được mô tả dưới dạng danh sách cạnh.

Sample Cases

Input #1:

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

Output #1:

3

Explanation #1:

Các cây con cân bằng là:

• Nút ~4~ (cây con trái ~=~ phải ~=~ ~0~, giá trị ~=~ ~4~).
• Nút ~5~ (cây con trái ~=~ phải ~=~ ~0~, giá trị ~=~ ~5~).
• Nút ~2~ (cây con trái ~=~ ~4~, phải ~=~ ~5~, tổng giá trị bằng nhau ~=~ ~9~).

Input #2:

7
1 1 1 1 1 1 1
1 2
1 3
2 4
2 5
3 6
3 7

Output #2:

7

Explanation #2:

Tất cả các nút đều tạo thành cây con cân bằng vì có cấu trúc đối xứng và giá trị bằng nhau.

Input #3:

3
1 2 3
1 2
1 3

Output #3:

2

Explanation #3:

Các cây con cân bằng là nút 2 và nút 3 (cây con trái = phải = 0).