COCI 2020/2021 - Contest 2 - Sjekira

View as PDF
Submit solution
Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Suggester:
NoobCpp
Problem source:
COCI 2020/2021 - Contest 2
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mirko cảm thấy rất mệt mỏi với công việc khi đảm nhiệm vai trò là CEO trong một công ty phần mềm đa quốc gia có tiếng. Anh ấy quyết định sẽ chuyển tới Gorski Kotar và sống cuộc sống đơn giản hơn. Tuy nhiên, mùa đông ở chốn làng quê xa xôi nơi anh mới chuyển đến này đang rất khó khăn. Không một người hàng xóm nào của anh được sinh ra sau Thế Chiến thứ II, vì vậy anh quyết định sẽ tự thân đốn củi.

Hôm nay, anh ấy sẽ chặt thân cây đầu tiên của anh. Trước khi chặt, anh chia thân cây thành các phần vừa đủ lọt vào lò sưởi, đánh số và đo độ cứng của chúng.

Mirko là một lập trình viên, vì vậy anh ấy nhận ra rằng các phần trên thân cây và sự kết nối giữa chúng tạo thành một đồ thị cây.

Chi phí tổn thất của chiếc rìu anh dùng để cắt một đoạn liên kết hai phần trên cây bằng tổng độ cứng lớn nhất của hai thành phần liên thông được tạo thành sau khi anh cắt đoạn liên kết đó.

Mirko chỉ có duy nhất ~1~ chiếc rìu, vì vậy anh ấy muốn tổng chi phí tổn thất càng nhỏ càng tốt. Anh ấy muốn biết tổng chi phí tổn thất nhỏ nhất lên chiếc rìu, nếu anh ấy chặt toàn bộ thân cây thành các phần riêng lẻ mà anh đã chia từ trước.

Input

Dòng đầu tiên chứa một số nguyên ~n~, số lượng các phần trên cây. Các phần sẽ được đánh số từ ~1~ đến ~n~.

Dòng thứ hai chứa ~n~ số nguyên ~t_i~ ~(1 \le t_i \le 10^9)~ - độ cứng của phần thứ ~i~.

~n - 1~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~x~ và ~y~ ~(1 \le x, y \le n)~ - chỉ số các phần được nối trực tiếp.

Output

Xuất ra tổng chi phí tổn thất nhỏ nhất sau ~n - 1~ lần chặt.

Sample 1

Input
3
1 2 3
1 2
2 3
Output
8

Sample 2

Input
4
2 2 3 2
1 3
3 2
4 3
Output
15

Sample 3

Input
5
5 2 3 1 4
2 1
3 1
2 4
2 5
Output
26

Subtask

  • ~5~ test đầu có ~1 \le n \le 10~.
  • ~10~ test sau input đảm bảo phần thứ ~i~ và ~i + 1~ ~(1 \le i \le n - 1)~ được nối trực tiếp.
  • ~5~ test sau có ~1 \le n \le 1000~.
  • ~10~ test cuối cùng có ~1 \le n \le 10^5~.

Giải thích ví dụ 1:

Có ~2~ cách để chặt thân cây này. Anh ấy có thể cắt đoạn liên kết ~(1, 2)~ trước, tổn thất ~1 + 3 = 4~, sau đó cắt đoạn liên kết ~(2, 3)~, tổn thất ~2 + 3 = 5~. Tổng chi phí tổn thất trong trường hợp này là ~9~.

Một cách khác, anh ấy có thể cắt đoạn ~(2, 3)~ trước, sau đó cắt đoạn ~(1, 2)~. Tổng chi phí tổn thất trong trường hợp này sẽ là ~(2 + 3) + (1 + 2) = 8~.

Comments

Please read the guidelines before commenting.


  • -6
    luongkhoi1111  commented on Dec. 18, 2024, 8:34 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    hieuhfgr  commented on Sept. 23, 2024, 11:49 a.m.

    Mô sai (my sol)

    Hint:

    Để chi phí nhỏ nhất thì ta cần tham lam các giá trị ~a_i~ trong TPLT phải là nhỏ nhất. -> Xóa dần dần những cạnh nối với ~i~ mà ~a_i~ đang là ~max~

    Solution:

    Nhận thấy để chi phí là nhỏ nhất thì ta sẽ xóa những cạnh nối với ~i~ mà ~a_i~ đang là lớn nhất. Bây giờ ta có danh sách các cạnh xóa.

    Bây giờ để tính chi phí thì ta có thể lật ngược lại danh sách cạnh xóa -> Bài toán trở thành tính chi phi khi nối những TPLT lại với nhau. Với hai đỉnh ~(u, v)~, ta xài DSU để lưu gốc và giá trị lớn nhất trong TPLT chứa ~u~ và chứa ~v~ và cộng cho kết quả như bình thường.

    lần 6 viết sol mong mọi ng đừng downvote T_T