想不到一点/ll 想不到一点/ll
首先考虑全是 1 的情况，不难想出一个贪心策略，每次选择深度最深的需要被覆盖的节点，然后倍增找到他的 $d$ 级祖先，记 $d$ 级祖先为 $p$，操作一次 $p$。容易发现这样一定不劣，因为这个节点一定要被干掉，操作 $p$ 的后代显然不如操作 $p$ 能处理的节点多。我也就只会这些了/ll。
然后看了看题解，发现这个思路是可以拓展的。我们记 $tim_u$ 表示 $u$ 这个节点距离最近的 0 节点的距离，不难发现只有 $tim_x>d$ 的 $x$ 才能被操作。我们考虑仍然是找到深度最深的需要被覆盖的节点 $u$，类比上面，发现最优方案是选择深度最浅的合法的 $v$ 操作。令 $p=lca(u,v)$，不难发现 $dep_v$ 最小的话，$dep_p$ 也会最小，所以 $p$ 子树能够被全部处理，当 $p$ 确定时，$dep_v$ 最小能够让 $p$ 子树外处理的最多，所以选择 $dep_v$ 最小的 $v$ 是最优的。所以我们就有了这样一个贪心的算法，暴力实现是 $O(n^2q)$ 的，结合特殊性质可以获得 $50$ 分。
上面已经说了对于每个 $p$ 要去寻找距离 $p$ 最近的 $v$，这个东西是可以 bfs 一遍预处理出来的。然后我们需要满足的条件就是 $dis(u,v)\leq d$。拆一下式子 $dep_u-dep_p+dis(p,v)\leq d$，也就是 $dep_p+d-dis(p,v)\geq dis_u$。发现前面的一堆东西只和 $p$ 有关，所以可以在 bfs 的过程中顺便预处理出来。然后需要找到满足这个条件的 $dep_p$ 最小的 $p$。设 $b_x=\max(dep_x+d-dis(x,v))$，容易发现 $b_{fa_x}\leq b_x$，因为给 $b_{fa_x}$ 的那个 $v$ 可以给 $x$ 用。所以只需要倍增找到深度最小的合法的 $p$，然后也就找到了需要操作的 $v$。
然后我们需要支持两种操作，把与 $x$ 距离 $\leq d$ 的点涂黑，求一个点是黑还是白。点分治经典问题。建出点分树然后对于每个点维护子树内到这个点距离 $\leq len_x$ 的点已经被涂黑的 $len_x$，修改的时候对于每个点分树上祖先更新 $len_x$，查询的时候查询自己是否会被点分树上每一个祖先所涂黑，时间复杂度 $O(nq\log n)$，常数不大，可以比较轻松地通过。