NGUỒN: PreVNOI Ⅶ Lần 2 (ONLINE 2017)
Cho một cây gồm đỉnh, mỗi đỉnh có một màu khác nhau. Gọi là số màu phân biệt trên đường đi từ đỉnh tới đỉnh . Đặt . Hãy tính với mọi đỉnh bất kì.
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên .
- Dòng thứ hai chứa số nguyên lần lượt là màu của các đỉnh.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và mô tả một cạnh của cây nối giữa hai đỉnh và . Dữ liệu vào đảm bảo đồ thị có dạng là cây.
Dữ liệu ra:
- Gồm dòng, dòng thứ chứa số nguyên .
Ví dụ:
Dữ liệu vào:
5
1 2 3 2 3
1 2
2 3
2 4
1 5
Dữ liệu ra:
Giải thích:
Giới hạn:
- với mọi
- Subtask #: số điểm:
- Subtask #: số điểm:
- Subtask #: số điểm: Mọi đỉnh có cùng màu
- Subtask #: số điểm: Không tồn tại hai đỉnh cùng màu
- Subtask #: số điểm: Không có ràng buộc gì thêm.
