PTREE - Cây P đỉnh ( Cơ bản )
Giới hạn- Thời gian: 0.152s
- Bộ nhớ: 1536MB
- Mã nguồn: 20000 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 cây gồm N đỉnh , mỗi đỉnh có 1 nhãn C[i] gọi là trọng số của đỉnh i . Hãy tìm 1 cây con gồm P đỉnh sao cho tổng trọng số của cây con này là lớn nhất . Hiểu 1 cách đơn giản là tìm P đỉnh sao cho P đỉnh này liên thông và tổng trọng số là lớn nhất .
Vì bài này là ở mức độ khó tuy nhiên lại có nhiều ứng dụng nên các bạn có thể xem lời giải, download test. Nói chung cũng có thể xếp bài này vào nhóm bài “cơ bản” .
Download test và solution tại
đây
.
Input
Dòng 1 : 2 số nguyên dương N và P . ( 1 ≤ P ≤ N ≤ 200 ) .
Dòng 2 : N số nguyên dương C[1] , … C[N] . ( -1000 ≤ C[i] ≤ 1000 ) .
N – 1 dòng tiếp theo , mỗi dòng gồm 2 số nguyên dương u , v mô tả 1 cạnh của đồ thị .
Output
Gồm 1 dòng ghi ra P số nguyên là chỉ số của P đỉnh được chọn .
Example
Input: 3 2 1 2 3 1 2 2 3 Output: 2 3
- Người up: hard7771988
- Nguồn bài: Folklore