Hướng dẫn giải của Bò Lân Cận

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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 $\leq 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 \cdot 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 $\leq r$ từ đỉnh $x$ .

$A [x] [0] = C [x]$ (chỉ bò tại đỉnh $x$ ).
Với $r \geq 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 $\leq 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 $\leq 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 $\leq 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 $\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 $(\deg (x) - 1) \cdot A [x] [r - 2]$ .

Thuật toán

$A [x] [r] = \sum_{y \in adj (x)} A [y] [r - 1] - (\deg (x) - 1) \cdot 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:

Đọc đồ thị, khởi tạo $A [\cdot] [0] = C [\cdot]$ .
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.
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ố $r mod 4$ (hoặc $r & 3$ ).

Độ phức tạp

Thời gian: $O (N \cdot 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.

Bình luận

Không có bình luận tại thời điểm này.