Editorial for Bedao Regular Contest 02 - TOURIST


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 dựng cây gốc ~A~, gọi các đỉnh trên đường đi từ ~A~ đến ~B~ lần lượt là ~u_1~, ~u_2~, ~\dots~ , ~u_k~

Ta thấy đáp án tối ưu sẽ có đường đi của ~A~ là từ ~A~ đến ~u_i~, rồi đi tiếp xuống một nhánh khác nhánh chứa đỉnh ~B~ và nhánh đó chứa nút lá có độ sâu lớn nhất trong số các nhánh anh em của nhánh chứa đỉnh ~B~, còn ~B~ sẽ đi trong cây con của ~u_{i+1}~

Gọi ~dp_u~ là kết quả tối ưu của ~B~ khi đi trong cây con gốc ~u~.

Gọi ~deep_u~ là khoảng cách xa nhất từ ~u~ đến một nút lá trong cây con gốc ~u~

Gọi ~h_u~ là độ sâu của nút ~u~ trên cây

Gọi ~ma_u~ là ~deep_v~ lớn nhất trong các ~v~ là con của ~u~ nhưng không phải là ~u_i~ nào đó

Ta có công thức tính ~dp_{u_i}~ như sau:

  • ~dp_{u_i} = deep_{u_i} + 1~ ( Nếu ~u_i = B~ )
  • ~dp_{u_i} = max(dp_{u_{i+1}}, h_B − h_u + ma_u + 2)~ ( Nếu ~ui \neq B~ )

Và với mỗi đỉnh ~u_1~, ~u_2~, ~\dots~, ~u_{k−1}~ ta cập nhập ~ans~ thành: ~max(ans,min(dp_u, h_u + ma_u + 1))~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.