Editorial for Bedao Grand Contest 10 - HOLIDAY


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

Ta có chi phí để di chuyển từ thành phố ~u~ đến thành phố ~v~ là tổng số lượng con đường và độ dài của chúng trên đường đi ngắn nhất từ ~u~ đến ~v~. Ta sẽ cộng độ dài của mỗi con đường tăng lên 1. Khi đó chi phí chính là tổng độ dài của các con đường từ ~u~ đến ~v~.

Vì đồ thị đã cho là một cây. Ta có thể sử dụng thuật toán đường kính để xử lí các truy vấn. Xét truy vấn có ~k_i~ đỉnh ~u_1, u_2, …, u_{k, i}~. Đầu tiên ta sẽ tìm đỉnh xa đỉnh ~1~ nhất trong ~k_i~ đỉnh trên, gọi đỉnh đó là ~U~. Sau đó ta sẽ tìm đỉnh xa đỉnh ~U~ nhất trên ~k_i~ đỉnh trên, gọi là ~V~. Độ dài của đường đi ~U~ đến ~V~ chính là đáp án của truy vấn.

Gọi ~dist_u~ là tổng độ dài đường đi từ ~1~ đến ~u~. Khi đó, để tìm đỉnh ~U~ xa đỉnh ~1~ nhất ta chỉ cần xét ~dist_{u_1}, dist_{u_2}, ..., dist_{u_{k_i}}~ trong ~O(k_i)~. Sau đó dùng công thức độ dài đường đi ~U~ đến ~V~ để tính đáp án trong ~O(k_i \times log_2(n))~ hoặc ~O(k_i)~ (tuỳ vào truy vấn tìm ~LCA~.

Vì ~\sum_{i=1}^{q} k_i \le n~ nên thuật toán có độ phức tạp là ~O(n \times log_2(n))~


Comments

Please read the guidelines before commenting.



  • 0
    adc   commented on Nov. 3, 2022, 9:34 p.m.

    mn cho em hỏi bài này phải code lca truy vấn O(1) mới qua được ạ


    • 0
      Person_A   commented on Nov. 3, 2022, 10:07 p.m.

      Mình làm O(log) vẫn qua được á bạn.


      • 0
        adc   commented on Nov. 4, 2022, 1:46 p.m.

        sao mình code o(log) mà tle nhỉ :(