Ynoi2001 梦想歌

zhouhuanyi · 2023-10-26 09:05:08 · 题解

首先容易发现将原树自底而上建立 \texttt{kruskal} 重构树后，相当于要对原树进行单点修改，动态维护重链剖分一个点所在的重链底。由于单点修改不是单点加，和 \texttt{ZJOI 2018} 历史不同，所以切换次数不是 O(n \log n) 的，所以可以考虑不维护出重链剖分而是直接求出重链底。注意到求 x 子树的带权重心其是容易的，因为重心的子树包含了至少一半的权值，所以如果将时间戳在 [\text{dfn}_{\text{x}},\text{dfn}_{\text{x}}+\text{sz}_{\text{x}}-1] 区间内的元素的带权中位数扣出来则其一定在至少一个重心的子树里，那么直接从这个点往上倍增即可找到带权重心。现在我们不断的将 x 跳到 x 子树的带权重心，由于带权重心一定在带权重链上，所以如果每一次跳到的带权重心均不是自己时一定可以跳到重链底，而当带权重心为自己时左右两边儿子的大小相同 (因为非叶节点权值为 0)，所以可以暴力的跳跃。注意到每次跳跃会使子树权值和减半，而子树权值和是 \leqslant 10^{18} 的，所以直接实现可以做到 O(n\log n+m\log n+q \log^2 n\log{\sum a_{i}})(m 为修改次数，q 为查询次数)，但可以采用分块维护子树和，于是可以做到 O(n\log n+m\sqrt n+q \log n\log{\sum a_{i}})。