大概有两种,第一种是魔改原官方题解做法,第二种则是直接避免(求出每个点的子树答案)。
算法一
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分。