3.8 模拟赛 A Bitset Master

题目连接

明显，我们可以用 Bitset 维护每个点的集合，复杂度是 $O(n^2 + \frac{nm}{w})$ 可以通过 50 分。

离线的那 20 分好像可以倒着合并啥的，不是很会，下面写正解了。

考虑这个询问，本质上就是从 $u$ 出发走 2 操作时刻单调递增的路径可以走到的 $v$ 的个数。先离线，把操作时刻挂在边于是我们就从一个维护点集的问题变成了一个路径问题。

考虑点分治，假设当前分治中心在 $u$ ，首先跑一次 dp ，求出从每个操作想要到达 $u$ 最快的时刻。这个 dp 很简单，从每个操作所在的边向上的的边上二分一下这个操作的时间转移即可。

然后我们按照每个点到达根的时间排序，从早到晚做一个类似扫描线的东西，同时我们维护一下从根到达每个点的时间，这个时间是会随着时间推移从小到大改变的，但是它的变化量是 $O(m)$ 的，所以我们可以用类似 dfs 去维护，如果当前这个点变晚了，那么就更新一下它的儿子，因此我们也需要对每个点的所有儿子按照当前时间维护一个 set。

为了统计答案，需要时刻算出当前从根到点时间小于 $t$ 的点的个数，这个可以 BIT 维护。

总复杂度是 $O((n+m)\log^2 n)$ ，点分治一次 $\log$ ，维护一次 $\log$ 。

然而没码完。。咕咕咕

这场 BC 题解都看不懂。。先咕了。。