CF1790F-Timofey and Black-White Tree-根号分块,暴力

· · 题解

CF1790F - Timofey and Black-White Tree

题意

给出一棵 n(2\leq n \leq 2\cdot 10^5) 个节点的树，最初 c_0 号节点是黑色，其余均为白色。

给定操作序列 c_1,c_2,\cdots,c_{n-1}，第 i 次操作表示将 c_i 号节点染黑。每次操作后，输出距离最近的两个黑点间的距离。

本题时限 4s。

思路

考虑暴力。

最坏的情况是：染黑的前 \sqrt {n} 个点均匀分布，各个点的距离为近似 \sqrt{n}，这一步骤复杂度是 O(n \sqrt n)。

接下来染黑的点，他到最近的其他点的距离一定 <\sqrt n。每次 BFS 时，控制入队的次数不超过上一次的答案（超过一定不会对答案产生更新），因此 BFS 的次数 <\sqrt n 次，这一步骤复杂度也是 O(n \sqrt n)。

因此，复杂度是 O(n \sqrt n)。

实现

需要注意的是：上面所讲的情况是特殊的极端情况。

实际情况可能是：某两个点距离非常近，某两个点距离非常远。每次 BFS 时，控制入队的次数即可。