题解：P16829 [AFOI 2025] F.树的价值

yzq_yzq · 2026-06-08 08:18:21 · 题解

对于操作 1，可以用 P9989 的势能线段树快速找到修改的位置。并且对于每个位置修改次数只有 \log V。

把修改拆成 (x,p)，代表给 a_x \rightarrow \frac {a_x} p，这样的修改总共只有 n \log V 次，考虑修改的贡献，应该是给一条从 x 到祖先的一条链的答案除以了 p，对于修改（链除单点查）可以用树状数组，对于找链的端点，假如原本是 p^k，那么其实只需要找到在 dfn 序列上 x 前后第一个包含 p^k 的位置 l,r，然后再从 x 倍增找到最后一个不包含 l,r 的点。

总复杂度 O(n \log n \log V)。