题意:
给定一棵树,初始时\(1\)号节点是红色的,要求支持两个询问:
题解:
对询问分块,假设块大小为\(B\).
每完成一个块后,用多源BFS更新每个节点离它最近的红色节点距离,复杂度为\(O(\dfrac{nm}B)\).
对每个操作\(2\),遍历块内所有在其之前的\(1\)操作对应结点,使用树上倍增求距离,复杂度为\(O(Bn\log n)\).
由均值不等式可得复杂度为\(O(n\sqrt{m\log n})\).
代码
原文：https://www.cnblogs.com/Heltion/p/13403279.html