#1489. TREE - Đếm cây

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: ĐỀ THI CHỌN HỌC SINH GIỎI THÀNH PHỐ BẢNG A VÀ CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA (TỈNH HẢI PHÒNG)
NĂM HỌC 2021 - 2022

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≤i≤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 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:

\left\{ \begin{array}{l} x < y\\ 2 \times M(x,y) < S(x,y) \end{array} \right.

Dữ liệu:

  • Dòng đầu là một số nguyên n\ (1≤n≤2×10^5) là số đỉnh của đồ thị;
  • Dòng tiếp theo gồm n số nguyên a_1,a_2,…,a_n\ (1≤a_i≤10^9) ;
  • n-1 dòng tiếp theo, mỗi dòng là hai số nguyên u,v\ (1≤u,v≤n) mô tả một cạnh nối giữa hai đỉnh u 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ụ:

Dữ liệu:

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

Kết quả:

6

Giải thích:

  • 6 cặp (x,y) thỏa mãn là: (2,3), (2,4), (2,5), (3,4), (3,5), (4,5) .

Dữ liệu:

5
10 3 8 1 2
1 2
1 3
2 4
2 5

Kết quả:

3

Giải thích:

  • 3 cặp (x,y) thỏa mãn là: (2,3), (3,4), (3,5) .

Giới hạn:

  • Subtask \#1: ( 30\% số điểm): n≤1000 ;
  • Subtask \#2: ( 10\% số điểm): a_i=1\ (1≤i≤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≤50000 ;
  • Subtask \#5: ( 30\% số điểm): Không có ràng buộc bổ sung.