Cho đồ thị vô hướng liên thông có \(n\) đỉnh (các đỉnh đánh số từ \(1\) đến \(n\)) và \(n - 1\) cạnh. Đỉnh \(i\) có trọng số là \(a_{i}\ (1 \leq i \leq n)\).

Gọi \(M(x,y)\) là trọng số lớn nhất của các đỉnh trên đường đi từ đỉnh \(x\) đến đỉnh \(y\) và \(S(x,y)\) là tổng trọng số của các đỉnh trên đường đi từ đỉnh \(x\) đến đỉnh \(y\).

Hãy đếm số cặp \((x,y)\ \)thỏa mãn

Dữ liệu vào:

• Dòng đầu là một số nguyên \(n\ (1 \leq n \leq {2 \times 10}^{5})\) là số đỉnh của đồ thị;

• Dòng tiếp theo gồm \(n\) số nguyên \(a_{1},a_{2},\ldots,\ a_{n}(1 \leq a_{i} \leq 10^{9})\);

• \(n - 1\) dòng tiếp theo, mỗi dòng là hai số nguyên \(u,\ v\ (1 \leq u,v \leq n)\) mô tả một cạnh nối giữa hai đỉnh \(u\) và \(v\).

Kết quả:

• Ghi ra một số duy nhất là số cặp \((x,y)\) thỏa mãn yêu cầu đề bài.

Ví dụ:

Chú ý:

• Subtask 1 (30% số điểm): \(n \leq 1000\);

• Subtask 2 (10% số điểm): \(a_{i} = 1\ (1 \leq i \leq n)\);

• Subtask 3 (20% số điểm): Không có đỉnh nào của đồ thị có bậc lớn hơn 2;

• Subtask 4 (10% số điểm): \(n \leq 50000\);

• Subtask 5 (30% số điểm): Không có ràng buộc bổ sung.