Trang trí đèn ba màu trên cây
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một mạng lưới gồm $N$ nút được nối với nhau thành một cây. Tại mỗi nút $u$, ta cần lắp một bóng đèn thuộc một trong ba màu $1, 2, 3$ với chi phí tương ứng là $c_{u,1}, c_{u,2}, c_{u,3}$. Để đảm bảo tính thẩm mỹ, không có hai nút nào nối trực tiếp với nhau bằng một cạnh được lắp bóng đèn cùng màu. Hãy tìm tổng chi phí nhỏ nhất để lắp đèn cho toàn bộ $N$ nút.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- $N$ dòng tiếp theo, dòng thứ $u$ chứa ba số nguyên $c_{u,1}, c_{u,2}, c_{u,3}$.
- $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một cạnh của cây.
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất tìm được.
Ví dụ
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 3 1 5 3 2 4 6 3 2 1 1 2 1 3 |
6 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le c_{u,k} \le 10^9$
Community Discussion