UOJ Logo zx2003的博客

博客

十二省联考D2T3 hope 不用求逆的做法

2019-04-12 18:15:28 By zx2003

大概有两种,第一种是魔改原官方题解做法,第二种则是直接避免(求出每个点的子树答案)。


算法一

2019.6.1upd:他假了,原因可以见lca的回复

在长链剖分的时候我们需要维护一个类似与滑动窗口的东西。

每次从滑动窗口里踢掉一个东西的时候,我们需要求出这个元素的真实值,官方题解在这里需要求逆。

但实际上每次遇到这种情况暴力$O(L)$地下传标记复杂度是对的。

证明的大概思路是,这样做的复杂度是链长+$\sum 每相邻两次的重叠长度$,然后对于每次重叠,一定存在一个短子树的深度大于等于重叠长度。

所以复杂度与长链剖分相同,仍为$O(n)$


算法二

一个自然的想法是通过树分治来规避求逆元。

但是一个很大的问题在于,我们仍然需要求出子连通块中的某个点到分治中心的答案,而且这一步相对于原问题没有任何简化。

我们能不能简化这一步呢?

注意到如果连通块直径不超过$L$,那么这一步是可以简单树上DP来完成的。

这就启示我们使用Top cluster 剖分。

我们可以将原树分割成$O(\frac{n}{L})$个直径不超过$L$的簇。

对于每个簇,可以预处理出,在簇的内部,两个端点的DP数组。

簇与簇之间的影响需要$O(\frac{n}{L})$次合并DP数组来计算。

合并两个DP数组的复杂度为$O(L)$,最后总复杂度为$O(\frac{n}{L} * L)=O(n)$


但是好像想要出个不能求逆的加强版比较困难,博主一时没想到有什么,不可逆,性质恰到好处,在本题中还能方便维护的信息。

算法一没有实现过,但应该是对的(吧)。

算法二的实现在这里->链接

由于滥用vector导致常数巨大,而且博主懒得卡常,所以只有80分。

评论

OldDriverTree
orz top cluster
lyx_cjz
模合数?
liu_cheng_ao
有道理!
liu_cheng_ao
但请问您的算法一如何处理自顶向下计算时对于原来 $f[i][L-\mathrm{dep}_i, L]$ 这一段真实值的访问呢?对 $f$ 下传标记之后,递归到子树内时无法继承标记下传的结果吧。
zx2003
幸好还有算法二。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。