Cây P đỉnh (Cơ bản)

Xem PDF

Điểm: 400 (p) Thời gian: 0.02s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Đề bài: 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.

Input

  • Dòng \(1\) : \(2\) số nguyên dương \(N\)\(P\) \((1 \le P \le N \le 200)\).
  • Dòng \(2\) : \(N\) số nguyên dương \(C_1, C_2, ..., C_N\) \((-1000 \le C_i \le 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

Test 1

Input
3 2
1 2 3
1 2
2 3
Output
2 3

Bình luận


  • 0
    huyhau6a2    6:47 p.m. 1 Tháng 7, 2022

    có ràng buộc gì xuất không, không thì tạo checker đi chứ nếu không có thì khó mà ac đó

    • 3 bình luận nữa