模拟赛 12 题解 | AlanSP's Blog

思维+贪心+双指针+换根dp+树上差分+树状数组

考场上这样贪心：每个鸟能跳多远跳多远。

把初始的 $L$ 个数作为鸟的数量，之后依次拓展能够到达的地方，把它们的承载量和当前鸟的个数取min作为后面的答案。

把拓展到的，还有剩余荷叶的地方扔进大根堆，每次取出最远的跳。

事实上是有 $O(n)$ 做法的，答案就是所有长度为 $L$ 的段的 $\min$ 。

证明可以感性理解，即跳的过程中每个 $L$ 鸟都要休息，短板原理。

我们发现答案是单调不降的，即区间左端点单调变化时右端点也是单调的。

这可以用双指针扫一遍，枚举左端点，统计合法区间个数。

查询区间或用st表 $O(1)$ 实现。

首先我们可以进行树上差分求出每个点的 $F(i)$ 。

具体而言就是在 $i$ 和向上走 $d_i+1$ 步的节点分别 $-a,+a$ ，最后树上前缀和就好了。

如果走出根就不减。

要维护 $E(F(i)^2)$ ，就要维护 $E(F(i))$ ，有公式：

E((F(a)+F(b))^2)\\=E(F(a)^2+2F(a)F(b)+F(b)^2)\\=E(F(a)^2)+2\times E(F(a))E(F(b))+E(F(b)^2)

我们可以先进行一遍dfs，求出子树内的 $E(F(i))$ 和 $E(F(i))^2$ 。

然后进行换根，求出整个连通块的答案。

注意：换根时要先减去该子树的贡献，然后再更新子树换根后的 $g$ 。

发现无论怎样旋转，树的中序遍历是不变的。

所以我们可以运用 $dfs$ 序的思想，让每个节点维护中序遍历上的一段区间。

查询可以直接乘积差分，但是旋转呢？

我们发现，旋转只影响 $x$ 和 $y$ 的区间，其他节点维护的信息不变。

具体分左旋右旋讨论一下区间是怎么变的就好了，画一下图，消除和增加对应位置的贡献。

由于是单点加，区间查询，我们可以用树状数组维护