Bò Lân Cận

Lời giải: Bò Lân Cận

Hướng tiếp cận

Bài toán yêu cầu tính, với mỗi đỉnh $x$ trên cây, tổng số bò trong khoảng cách $\le K$ cạnh từ $x$.

Cách tiếp cận trực tiếp — với mỗi đỉnh $x$, BFS/DFS sâu $K$ tầng — có độ phức tạp $O(N·K)$ với hằng số lớn. Tuy nhiên, có một công thức DP thanh lịch hơn trên cây.

Nhận xét quan trọng

Định nghĩa $A[x][r]$ = tổng số bò trong khoảng cách đúng bằng $\le r$ từ đỉnh $x$.

• $A[x][0]=C[x]$ (chỉ bò tại đỉnh $x$).
• Với $r\ge 1$: Xét tất cả các hàng xóm $y$ của $x$. Mỗi hàng xóm $y$ biết số bò trong khoảng cách $\le r-1$ từ $y$, tức là $A[y][r-1]$. Tổng này chứa mọi đỉnh trong khoảng cách $\le r$ từ $x$ nhưng đi qua $y$.

Vấn đề: khi cộng $A[y][r-1]$ cho mọi hàng xóm $y$, đỉnh $x$ bản thân nó và các đỉnh trong khoảng cách $\le r-2$ từ $x$ bị đếm nhiều lần — mỗi hàng xóm đều "nhìn thấy" những đỉnh này.

Cụ thể, $A[x][r-2]$ bị đếm $\mathrm{deg}(x)$ lần (mỗi hàng xóm đóng góp 1 lần), nhưng ta chỉ muốn đếm 1 lần. Do đó ta trừ đi $(\mathrm{deg}(x)-1)·A[x][r-2]$.

Thuật toán

$$A[x][r]=\sum _{y\in \text{adj}(x)}A[y][r-1]-(\mathrm{deg}(x)-1)·A[x][r-2]$$

Công thức này chính xác trên cây vì không có chu trình — mỗi đường đi duy nhất, nên việc loại trừ kép được đơn giản hóa như trên.

Cài đặt:

1. Đọc đồ thị, khởi tạo $A[·][0]=C[·]$.
2. Lặp $r$ từ 1 đến $K$: với mỗi đỉnh $x$, tính $A[x][r]$ theo công thức trên.
3. In $A[i][K]$ cho mỗi $i$.

Tối ưu bộ nhớ: Chỉ cần lưu 3 lớp $r$ (lớp hiện tại, lớp $r-1$, lớp $r-2$) bằng mảng xoay (rolling array) kích thước 4, truy cập bằng chỉ số $rmod4$ (hoặc $r<mrow><mi>\&</mi></mrow>3$).

Độ phức tạp

• Thời gian: $O(N·K)$ — vòng lặp $K$ tầng, mỗi tầng duyệt $O(N)$ đỉnh với tổng bậc $O(N)$.
• Bộ nhớ: $O(N)$ — chỉ lưu 4 lớp DP, mỗi lớp $N$ phần tử.

Với $N={10}^5$ và $K=20$, thuật toán thực hiện khoảng $2\times {10}^6$ phép tính — rất nhanh.