【YNOI2012】D2T2

一道不难想而且代码较短的$YNOI$题。所以为什么都没人写写$YNOI$了啊,感觉$YNOI2012$冷清清的。

拿过来一看,这个操作$1$感觉就很麻烦。子树先看成$dfs$序。模$x$等于$y$,这种操作好像也没有什么数据结构可以维护(可能是我孤陋寡闻了?),于是考虑暴力。

有一种显然的暴力就是直接对时间轴分块,然后询问的时候就遍历$O(B)$个修改,看看是否影响当前询问点。每$B$个修改就暴力更新一下,即对于每个修改每次一直跳$x$的深度,然后更新一下这些点。

这样跳有很多不好的地方,比如同一深度如果点很多就会越跳越多。于是我们稍微优化一下,按$dfs$序遍历每个询问,然后只维护模$x$等于$y$的深度上的权值,这样复杂度就是$O(n+B\ast \frac{n}{x})$,稍微注意一下不在一棵子树就要去掉之前贡献的细节。这样总复杂度就是($n,m$同阶)$O(\frac{n}{B}(n+B\ast \frac{n}{x})+nB)$,即$O(\frac{n^2}{B}+\frac{n^2}{x}+nB)$。但这个$x$毕竟是$[1,n]$的,复杂度就会退化到$O(n^2)$了。

注意到当$x$比较小的时候,我们对$dfs$序分块有奇效。我们在每个块里维护一个二维数组$sum[x][y]$,表示当前块内模$x$等于$y$的点要加$sum[x][y]$的权值。显然这个当$x$比较小的时候能开的下。于是设个阈值$lim$,当$x\leq lim$的时候维护$dfs$序分块,否则继续对时间轴分块。这样时间复杂度就是$O(\frac{n^2}{B}+\frac{n^2}{lim}+nB+n\sqrt{n})$,在$B$取$\sqrt{n}$,$lim$取$\sqrt{n}$时最优,做到$O(n\sqrt{n})$,只不过此时空间复杂度是$O(n\ast lim)$,所以且行且珍惜。

其实删去其他子树贡献这个细节挺难写的。。。