VM 15 Bài 15 - Cắt cây

Xem dạng PDF
Gửi bài giải
Điểm: 1,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
VM15 - Minh
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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.

Sample 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

Sample Output

20

Note

  • ~0 \le K < N \le 10^{5}~
  • ~0 < w_{i} \le 10^{4}~
  • Trong ~20\%~ số test, ~N \le 20~
  • Trong ~20\%~ số test tiếp theo, ~N \le 200~
  • Trong ~20\%~ số test tiếp theo, ~N \le 1000~, trọng số các đỉnh bằng ~1~.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 5
    pppssslc  đã bình luận lúc 21, Tháng 6, 2025, 2:11 ← sửa 5

    spoil

    DFS + Tham lam + chặt nhị phân:

    • Gọi các đỉnh con của ~u~ là ~v~.
    • Gọi ~S(u)~ là tổng trọng số cây con gốc ~u~.
    • Gọi số lần cắt đối với mỗi giá trị ~x~ là ~cnt~;
    • Chặt nhị phân giá trị ~x~ trong khoảng từ ~0~ tới ~10^9~.
    • ~cnt ≤ k~ thì giá trị ~x~ thỏa mãn
    • ~x~ càng lớn thì ~cnt~ càng bé → càng dễ thỏa mãn.
    • DFS để tính ~S(u)~.
    • Nếu ~S(u) > x~:
    • Ưu tiên cắt các cạnh ~u, v~ có ~S(v)~ lớn trước.
    • Sau khi cắt cạnh ~u, v~ thì ~S(u) = S(u) - S(v)~.
    • sau mỗi lần cắt thì tăng ~cnt~ lên ~1~.
    • Cắt đến khi ~S(u) ≤ x~ hoặc ~cnt > k~.

    Độ phức tạp: ~O(n*log_2n*30)~