VMCUT2 - Cắt cây
Giới hạn- Thời gian: 1.0s
- 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.
Cho một đồ thị dạng cây gồm N đỉnh, đỉnh thứ i có trọng số là w[i]. Cho K lần cắt cây (bằng cạnh xóa đi 1 cạnh đang có), ta sẽ tạo ra một rừng gồm K+1 cây. Trọng số của một cây được định nghĩa là tổng trọng số các đỉnh trong cây đó.
Bài toán yêu cầu bạn hãy tìm cách cắt cây sao cho trọng số to nhất của các cây là nhỏ nhất.
Input
Dòng đầu tiên gồm 2 số N, K (K < N)
Dòng tiếp theo gồm N số là trọng số của các đỉnh
N-1 dòng tiếp theo, mỗi dòng gồm 2 số u, v mô tả một cạnh của cây
Output
Một số nguyên duy nhất là trọng số bé nhất.
Giới hạn
- 0 <= K < N <= 10^5
- 0 < w[i] <= 10^4
- Trong 20% số test, N <= 20
- Trong 20% số test tiếp theo, N <= 200
- Trong 20% số test tiếp theo, N <= 1000, trọng số các đỉnh bằng 1.
Sau khi kết thúc kỳ thi, kết quả của bạn là kết quả lần nộp bài cuối cùng
Example
Input:
8 2 7 4 3 8 5 7 5 4 2 1 3 1 4 3 5 2 6 1 7 6 8 1
Output:
20
- Người up: voj
- Nguồn bài: VM15 - Minh