点分治，问题变成将一个子树的深度加上一个数，以及询问有多少个点的深度不超过 $d$。
用 DFS 序转化到序列上然后分块，单次操作时间复杂度根据实现是 $O(\sqrt n\log n)$ 到 $O(\sqrt n)$ 不等。在点分树上每次需要操作到根的 $\log n$ 个点，但是因为大小每次减半，总时间复杂度不变，还是 $O(\sqrt n\log n)$ 到 $O(\sqrt n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #155 for Problem #6737. Neighbourhood
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-12 23:38:10
Last updated: 2025-12-12 23:38:14
题解
Comments
No comments yet.