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ó đỉnh (các đỉnh đánh số từ đến ) và cạnh. Đỉnh có trọng số là .
Gọi là trọng số lớn nhất của các đỉnh trên đường đi từ đỉnh đến đỉnh và là tổng trọng số của các đỉnh trên đường đi từ đỉnh đến đỉnh .
Hãy đếm số cặp thỏa mãn:
Dữ liệu:
- Dòng đầu là một số nguyên là số đỉnh của đồ thị;
- Dòng tiếp theo gồm số nguyên ;
- dòng tiếp theo, mỗi dòng là hai số nguyên mô tả một cạnh nối giữa hai đỉnh và .
Kết quả:
- Ghi ra một số duy nhất là số cặp 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ả:
Giải thích:
- cặp thỏa mãn là: .
Dữ liệu:
5
10 3 8 1 2
1 2
1 3
2 4
2 5
Kết quả:
Giải thích:
- cặp thỏa mãn là: .
Giới hạn:
- Subtask ( số điểm): ;
- Subtask ( số điểm): ;
- Subtask ( số điểm): Không có đỉnh nào của đồ thị có bậc lớn hơn ;
- Subtask ( số điểm): ;
- Subtask ( số điểm): Không có ràng buộc bổ sung.
