[POI2015]Odwiedziny

感觉自己代码能力好弱啊……

题目页面(luogu)

这题实际上比较套路……

注意到 $n\le 50000$,大概率是想让我们用个 $\mathcal{O}(n\sqrt{n})$ 的复杂度。想到根号复杂度的话就很有可能是个根号分治。这题也不例外。

我们按照 $k$ 的大小分成两类:假设一个界为 $B=200$,当 $k\ge B$ 的时候就可以直接暴力模拟这个跳的过程,当 $k<B$ 的时候就可以考虑用什么东西来维护。

先说简单的部分:暴力向上跳。我们可以将路径 $x\to y$ 拆成 $x\to lca,lca \to y$。这样的话,我们需要距离 $x$ 为 $k$ 的祖先是哪一个(也就是 $x$ 的 $k$ 级祖先)。这一部分我们可以用长链剖分来搞,虽然慢了点但还是能过。这样的话,就可以将路径看成 $x$ 到 $lca$,$y$ 到 $lca$。

注意一个细节:$y$ 需要先往上跳一小段再暴力跳到 $lca$,因为题目中有说 “距离小于 $k$ 的话就直接一步跳到 $y$”。这样的话,因为 $y$ 往上跳与实际路径方向相反,所以需要先处理这一小段。

之后再说 $k<B$ 的部分。设 $s(i,j)$ 表示从 $i$ 开始每次跳 $j$ 步一直跳到根节点为止的路径上的点权和(当然也有可能跳不到根节点,但这个其实无所谓,因为这个时候再跳 $j$ 步的话已经跳出去了)。这一步有一个递推式子:设 $f(i,j)$ 表示 $i$ 的 $j$ 级祖先是哪个点,那么显然我们就有 $s(i,j)=s(f(i,j),j)+a_i$($a_i$ 为点权),注意 $f(i,j)$ 可能不存在,这个时候就是 $s(i,j)=a_i$。

之后,我们可以算出 $s(x,k)$ 并减去在 $lca(x,y)$ 上方的部分贡献,同理也可以算出 $s(y,k)$ 并减去在 $lca(x,y)$ 上方的部分贡献。

综上,这个题就做完了。

但是这题细节是真的超多……

 

发表评论