go where i belongyou don't belong.

拍照搜题秒出答案,一键查看所有搜题记录

拍照搜题秒出答案,一键查看所有搜题记录

构建:像线性的莫队那样依旧昰按sqrt(n)为一块分块。

然后呢我们可以发现一些树上莫队的性质:

用S(v, u)代表 v到u的路径上的结点的集合。

用root来代表根结点用lca(v, u)来代表v、u的最近公囲祖先。

其中xor是集合的对称差

简单来说就是节点出现两次消掉。

lca很讨厌于是再定义

由于对称差的交换律、结合律:

按照以上方式,我們就可以每次从u1走到u2,v1走到v2然后要求query的时候对他们的公共祖先的存在性取反,然后求完答案后再取反回去

拍照搜题秒出答案,一键查看所有搜题记录

拍照搜题秒出答案,一键查看所有搜题记录

我要回帖

更多关于 where i belong 的文章

 

随机推荐