(Giả sử thiết bị quan sát là camera)

Subtask 1: Liệt kê \(2^n\) trường hợp.

Subtask 2: DP , xác định mảng dp \(f[i][j][k][l]\).

\(f[i][j][k1][k2]\) chỉ ra rằng cây con của nút thứ i đã được xử lý và j camera được đặt trong cây con.

Điểm xa nhất dự kiến ​​quan sát được nhưng không quan sát được là \(k1\), khoảng cách từ camera gần nhất đến \(i\) là \(k2\).

Độ phức tạp của \(DP\) có thể là \(O(n^4)\).

Subtask 5:

Trong quá trình DP, chúng ta khởi tạo mỗi nút có \(3\) trạng thái:

• không có gì xảy ra.
• có camera.
• mặc dù không có camera nhưng điểm này sẽ được quan sát sau.

Thông tin hữu ích của nó là: khoảng cách của camera gần điểm \(i\) nhất trong cây con, camera dự kiến ​​được quan sát xa điểm \(i\) nhất trong cây con.

Khoảng cách điểm và thông tin hữu ích khi và chỉ khi khoảng cách \(\le r\), vì phạm vi quan sát của camera là \(r\).

Nếu có hai thông tin đồng thời tồn tại, thông tin camera có thể bị bỏ qua.

Chứng minh điều đó ở đây:

Gọi điểm xa nhất dự kiến ​​quan sát được là điểm \(a\). Camera gần nhất là điểm \(b\). Vậy \(dis(a,b)>r\).

Sau đó, phải có điểm máy ảnh \(c\) sao cho \(dis(a,c)<=r\). Sau đó, rõ ràng là \(dis(c,i)<dis(b,i)\). Rõ ràng, các điểm bên ngoài cây con \(i\) mà camera \(b\) có thể quan sát được thì camera \(c\) cũng có thể quan sát được.

Vì vậy, thông tin của \(b\) có thể được bỏ qua, tất nhiên, mảng \(DP\) có thể được viết là \(f[i][j][k]\) (chiều thứ ba và thứ tư ban đầu được nén thành một chiều).

Điều này là không đủ, bởi vì \(n \le 1000\).

Ta cũng cần chứng minh rằng khi \(n \le k*r\) thì quan sát được mọi điểm.

Chỉ cần chọn một điểm để đề cập đến gốc rễ. Lấy điểm có độ sâu lớn nhất, nếu độ sâu \(\le r\) thì chọn trực tiếp nút gốc để đặt camera.

Nếu độ sâu \(dep>r\) thì chọn \(lca\) cách điểm là \(r\), và chọn tổ tiên để đặt camera, tương đương với việc bỏ ra camera để chặt một cây con có điểm \(>=r\).

Dễ dàng chứng minh được khi \(n \le k*r\) quan sát được mọi điểm.

Do đó, khi \(k * r<n\), liệt kê điểm \(i\), và lần lượt hợp nhất các cây con được đại diện bởi các con của nó. Độ phức tạp là \(O(min(k, size[a])*min(k, size[b])*r)\).