Cộng đường đi trên cây

Hướng tiếp cận

Áp dụng kĩ thuật mảng hiệu trên cây (tree difference array) — phiên bản cộng theo đường đi của difference-array một chiều.

Nhận xét quan trọng

Với mỗi thao tác $(u,v,w)$, gọi $L=\mathrm{l}\mathrm{c}\mathrm{a}(u,v)$. Ta tăng một mảng $d[·]$ như sau:

Sau khi xử lí xong tất cả thao tác, giá trị cuối tại đỉnh $x$ chính là tổng $d[y]$ với $y$ chạy trên toàn bộ cây con gốc $x$:

$$\text{val}(x)=\sum _{y\in \text{subtree}(x)}d[y].$$

Vì sao đúng? Xét một đường đi $u\to v$ với LCA là $L$. Với mỗi đỉnh $x$ trên cây, ta cần chứng minh tổng $d$ trong cây con của $x$ bằng $w$ nếu $x$ nằm trên đường đi và bằng $0$ nếu không.

• Nếu $x$ nằm trên đoạn $u$–$L$ (không kể $L$): cây con $x$ chứa $u$ nhưng không chứa $v,L,\mathrm{p}\mathrm{a}\mathrm{r}(L)$ → tổng $=w$.
• Nếu $x=L$: cây con chứa $u,v,L$ nhưng không chứa $\mathrm{p}\mathrm{a}\mathrm{r}(L)$ → tổng $=w+w-w=w$.
• Nếu $x$ nằm trên đoạn $v$–$L$ (không kể $L$): tương tự → tổng $=w$.
• Nếu $x$ là tổ tiên thực sự của $L$: cây con chứa cả $u,v,L,\mathrm{p}\mathrm{a}\mathrm{r}(L)$ → tổng $=w+w-w-w=0$.
• Các trường hợp khác (không liên quan): tổng $=0$.

Trường hợp $u=v$ (đường đi 1 đỉnh): $L=u$ nên hai lần và một lần, tổng vẫn cho đúng $w$ tại $u$.

Thuật toán

1. Đọc cây, dựng danh sách kề.
2. BFS từ gốc, ghi depth[v], parent[v] và thứ tự BFS để sau dùng cộng cây con từ lá lên.
3. Dựng binary lifting up[k][v] với $k=0..\lceil {\log }_{2}N\rceil$ để truy vấn LCA trong $O(\log N)$.
4. Với mỗi thao tác $(u,v,w)$:
   • Tính $L=\mathrm{l}\mathrm{c}\mathrm{a}(u,v)$.
   • , , , nếu $\mathrm{p}\mathrm{a}\mathrm{r}(L)\ne 0$ thì .
5. Duyệt các đỉnh theo thứ tự ngược của thứ tự BFS (con trước cha), với mỗi đỉnh không phải gốc cộng $d[v]$ vào $d[\mathrm{p}\mathrm{a}\mathrm{r}(v)]$. Khi xong, $d[v]$ chính là $\text{val}(v)$.
6. In ra $d[1],d[2],\dots ,d[N]$.

Độ phức tạp

• Thời gian: $O((N+Q)\log N)$.
• Bộ nhớ: $O(N\log N)$ cho binary lifting.