Cách 1: Heavy-Light Decomposition

Nếu ta dùng cổng dịch chuyển tại đỉnh \(u\), rõ ràng ta sẽ dịch chuyển ngay về đỉnh \(1\) (nhận xét của bài Travel1)

Để đi từ \(v\) tới \(1\), ta có hai cách : đi trực tiếp - chi phí chính là độ sâu của nút \(v\). Cách thứ hai là đi từ \(v\) tới \(u\) rồi dùng cổng dịch chuyển ở \(u\).

Như vậy, với mỗi \(v\), ta cần tìm min của biểu thức chi phí \(C = dist(u,v) + cost[u]\)

Chia làm 2 trường hợp :

• Đỉnh \(u\) nằm trong cây con gốc \(v\) : \(dist(u,v) = depth[u] - depth[v]\). Do đó \(C = depth[u] + cost[u] - depth[v]\) nên ta chỉ cần tìm nút \(u\) trong cây con gốc \(v\) có \(depth[u] + cost[u]\) nhỏ nhất là được. (về cài đặt, chỉ cần đánh dấu theo thứ tự thăm DFS thì những đỉnh trong cây con mỗi gốc \(v\) sẽ luôn nằm ở những vị trí liên tiếp --> Segment Tree)
• Đỉnh \(u\) nằm ngoài cây con gốc \(v\) : Gọi \(w = lca(u,v)\), như vậy chi phí là \(C = depth[v] + depth[u] - 2*depth[w] + cost[u]\)

--> Mỗi nút \(x\) trong segment tree lưu hai thông tin : \(min(depth[u] + cost[u])\) với \(u\) là nút con cháu của mọi đỉnh \(w\) của cây trong đoạn quản lí của nút \(x\). (Xin được nhắc lại chút là trong cách cài đặt của HLD, những đỉnh thuộc cùng một "Heavy chain" sẽ nằm liên tiếp nhau).
Thông tin thứ hai là min của biểu thức \(C\) (với mỗi nút \(w\)).

Để rõ ràng hơn, mình xin được mô hình hóa bài toán này dưới dạng dãy số :

• Cho 2 dãy \(a[n]\) và \(b[n]\) (\(a[n]\) ở đây là -2*độ_sâu[nút w], \(b[n]\) chính là depth[u] + cost[u])
• \(a[n]\) cố định, cần thực hiện \(q\) truy vấn thuộc hai loại
• Truy vấn loại 1 : cập nhật \(b[L..R]\) theo \(val\) : với mỗi \(i, L \le i \le R\), gán \(b[i] = min(b[i], val)\)
• Truy vấn loại 2 : lấy min của \(a[i] + b[i]\) trong đoạn \([L,R]\)

Cách 2 : Centroid Decomposition

Ta dựng trước cây Centroid \(T'\) từ cây gốc. Theo tính chất, độ cao của cây \(T'\) này không vượt quá \(log_2(n)\)

(-----đang viết-----)