Xử lí online các truy vấn

• Truy vấn 1: Đặt r=gốc
• Truy vấn 2: kết quả nằm trong 6 kết quả sau:
  • +) u, v, r, lca(u,v), lca(u,r), lca(v,r).
  • Có một nhận xét là nếu r' là cha chung gần nhất của (u,v) mà r đang là gốc thì tổng khoảng cách từ r' tới u, r' tới v, r' tới r phải nhỏ nhất

Chú ý ban đầu đặt r=1

Vậy với mỗi truy vấn 1 thì mình ko cần duyệt dfs phải ko a ?

Xử lí online các truy vấn

• Truy vấn 1: Đặt r=gốc
• Truy vấn 2: kết quả nằm trong 6 kết quả sau:
  • +) u, v, r, lca(u,v), lca(u,r), lca(v,r).
  • Có một nhận xét là nếu r' là cha chung gần nhất của (u,v) mà r đang là gốc thì tổng khoảng cách từ r' tới u, r' tới v, r' tới r phải nhỏ nhất

Chú ý ban đầu đặt r=1