Editorial for Bedao Regular Contest 01 - HOGWARTS


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Bài toán: Cho ~n~ đỉnh và ~m~ cạnh, mỗi cạnh đều có trọng số là ~w_i~, ~q~ truy vấn yêu cầu

  • ~C~ ~i~ ~W~ là thay đổi trọng số đỉnh thứ ~i~ thành ~W~
  • ~D~ ~j~ là xóa đi cạnh thứ ~j~ trong đồ thị ban đầu ( đương nhiên cạnh này phải là cạnh xuất hiện trong đồ thị ngay từ đầu )

Ta cần đi tìm thành phần liên thông có tổng trọng số các đỉnh là lớn nhất trong các thành phần liên thông tồn tại tại thời điểm đó.

Nhận xét 1: Lật ngược lại bài toán, ta thực hiện ngược các truy vấn. Chính vì đã thực hiện ngược các truy vấn nên ta cần khôi phục lại đồ thị ban đầu, việc khôi phục bắt đầu từ đồ thị sau khi đã thực hiện ~q~ truy vấn. Biết rằng đồ thị sau khi đã thực hiện ~q~ truy vấn là đồ thị bị xóa hết cạnh ở thao tác ~D~ ~j~ và thay đổi hết trọng số đỉnh ở thao tác ~C~ ~i~ ~W~.

Nhận xét 2: Khi đã có đồ thị sau khi thực hiện ~q~ truy vấn, thao tác ~D~ ~j~ là xóa cạnh ~j~ giờ đây sẽ là thêm cạnh ~j~ vào đồ thị, tương tự thao tác ~C~ ~i~ ~W~ là biến từ trọng số ~w~ thành ~W~ giờ đây sẽ là biến từ trọng số ~W~ về lại trọng số ~w~. Do bài toán thực hiện offline nên ta sẽ phải lưu đáp án.

Gọi ~sum_u~ là tổng trọng số của thành phần liên thông có đỉnh u là đại diện

Thao tác ~D~ ~j~ thêm cạnh có thể thực hiện bằng DSU, vậy khi thêm một cạnh vào là ta nối đỉnh ~u~ và đỉnh ~v~ thuộc ~2~ thành phần liên thông khác nhau vào thành ~1~ thành phần liên thông

-> ~sum_u + sum_v~

Thao tác ~C~ ~i~ ~W~ sẽ là trực tiếp thay đổi trọng số của đỉnh ~i~, việc thay đổi trọng số của đỉnh ~i~ từ ~W~ về ~w~ cũng sẽ dẫn đến ~sum_i~ thay đổi một lượng từ ~W~ về ~w~

-> ~sum_i = sum_i - W~, ~sum_i = sum_i + w~

Vậy để biết thành phần liên thông chứa trọng số lớn nhất có thể duy trì bằng một Multiset.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.