Tổng đường đi trên cây (LCA)

Hướng tiếp cận

Đây là bài toán truy vấn tổng trọng số đỉnh trên đường đi giữa hai đỉnh trên cây. Ta dùng kỹ thuật tổng tiền tố trên cây kết hợp với LCA (Lowest Common Ancestor).

Nhận xét quan trọng

Gọi $\text{pref}[u]$ là tổng trọng số của các đỉnh trên đường đi từ gốc $1$ đến đỉnh $u$ (gồm cả $u$). Với hai đỉnh $u,v$ và $l=\text{LCA}(u,v)$:

• Đường $u\to v$ là hợp của đường $l\to u$ và đường $l\to v$, giao tại đúng đỉnh $l$.
• Tổng = $\text{pref}[u]+\text{pref}[v]-2·\text{pref}[l]+w_l$.

Lý do: $\text{pref}[u]-\text{pref}[l]$ là tổng các đỉnh từ con của $l$ trên đường tới $u$ cho đến $u$ (không gồm $l$). Tương tự với $v$. Cộng lại rồi thêm $w_l$ chính là tổng cần tìm.

Thuật toán

1. DFS (lặp, dùng stack) từ gốc $1$ để tính $\text{depth}[u]$, $\text{parent}[u]$, $\text{pref}[u]=\text{pref}[\text{parent}[u]]+w_u$.
2. Binary lifting: dựng bảng $\text{up}[k][u]$ = tổ tiên thứ $2^k$ của $u$, với $k=0,1,\dots ,\lceil {\log }_{2}n\rceil$. Truy hồi $\text{up}[k][u]=\text{up}[k-1][\text{up}[k-1][u]]$.
3. LCA$(u,v)$: nâng đỉnh sâu hơn lên cho cùng độ sâu, sau đó nâng đồng thời từng bậc $2^k$ giảm dần đến khi hai con trỏ chỉ vào hai đỉnh có cha chung.
4. Trả lời truy vấn bằng công thức trên.

Độ phức tạp

• Tiền xử lý: $O(n\log n)$.
• Mỗi truy vấn: $O(\log n)$.
• Tổng: $O((n+q)\log n)$, phù hợp với $n,q\le 2·{10}^5$.