题解：P12536 [XJTUPC 2025] 我永远喜欢希儿·芙乐艾

_Kenma_ · 2025-05-20 15:58:24 · 题解

前言

提供一种比官解劣的做法。

用一节 whk 自习口胡出来的。

思路分析

首先换根是假的，我们依然维护以 1 为根的子树和即可。

考虑根号相关数据结构。

把 A 分块，块长为 B，那么我们分散块和整块考虑。

对于散块，散块的总块长之和为 O(nB)，这一部分直接维护链加子树和，使用树上差分相关套路做到 O(nB\log n)。

对于整块，我们预处理系数 b_{i,j} 表示进行第 i 块内加 1，第 j 个点的子树会加 b_{i,j}。b 的处理可以树上差分求两次子树和做到 O(\frac{n^2}{B})。

因为要求空间线性，所以我们需要逐块处理。

总体复杂度为 O(nB\log n+\frac{n^2}{B})，平衡复杂度后为 O(n \sqrt{n \log n})。

关于链加子树和的维护，也可以使用更简单的树剖 + BIT，总体复杂度为 O(nB\log^2 n+\frac{n^2}{B})，平衡复杂度后为 O(n \sqrt{n} \log n)，常数很小。