KINGDOM - Đế chế hùng mạnh nhất
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Thời xưa có N đế chế tọa lạc trên một vùng đất xa xăm nọ, chiến đấu tranh giành lẫn nhau. Vua của đế chế hùng mạnh nhất quyết định chinh phục các đế chế khác để tìm kiếm nguồn dầu hỏa! Kho tàng của đế chế này bị hạn chế vì tiền đã được đổ vào chiến dịch tranh cử mới nhất của nhà vua. Kho tàng ban đầu có giá trị là M.
Các đế chế được đánh số từ 1 đến N. Đế chế 1 là đế chế hùng mạnh nhất. Các đế chế được nối với nhau bởi các đường nối hai chiều trong đó chỉ có đúng một đường đi giữa hai đế chế bất kỳ.
Nhà vua thuê bạn để hoạch địch chiến lược cho ông. Các điệp viên của nhà vua cho bạn hai thông số đối với mỗi đất nước i (i>1):
- V i = giá trị của nguồn dầu hỏa của nước i
- C i = chi phí để chinh phục nước i
Một đế chể chỉ có thể bị chinh phục khi nó kề với đế chế 1 hoặc đế chế 1 đã chinh phục một đế chế kề với nó (nối với nó qua một con đường).
Bạn hãy hoạch địch một chiến lược chinh phục các đế chế khác sao cho tổng giá trị thu được từ nguồn dầu hỏa là lớn nhất. Không được sử dụng quá giới hạn của kho tàng!
Dữ liệu
- Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 100) và M (0 ≤ M ≤ 2000).
- Dòng thứ hai chứa N-1 số nguyên V 2 , V 3 ..., V N (1 ≤ V i ≤ 100).
- Dòng thứ ba chứa N-1 số nguyên C 2 , C 3 ,..., C N (0 ≤ C i ≤ 30).
- Mỗi dòng trong N-1 dòng tiếp theo chứa hai số nguyên u, v thể hiện một đường nối.
Kết quả
Một số nguyên duy nhất là tổng giá trị lớn nhất từ nguồn dầu hỏa mà đế chế hùng mạnh nhất có thể thu được bằng việc chinh phục các nước khác.
Ví dụ
Dữ liệu 10 3 10 10 10 9 5 8 8 7 10 0 0 0 0 0 3 2 2 0 1 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 8 10 Kết quả 62 Dữ liệu 3 1 1 1 1 0 1 2 2 3 Kết quả 2
- Người up: voj
- Nguồn bài: VNOI Marathon '08 - Round 12/DivAProbem Setter: Sharif Shah Newaj Bhuiyan