CF1749F Distance to the Path

Alex_Wei · 2022-12-03 11:30:39 · 题解

这道题太 OI 啦！

观察发现 d 很小，我们要利用这一点。

以 1 为根，维护 f_{d, i} 表示 i 子树内距离 i 为 d 的所有节点被加上的值，则查询 v 时，对 v 的 k 级祖先 u 求 \sum f_{k, u}。

设 A(u, d) 表示 u 子树内距离 u 不大于 d 的点集。

考虑一次修改 (u, v, k, d)，设 x = \operatorname{lca}(u, v)。则 A(u, d) 会受到贡献，但 A(fa_u, d) 同样会受到贡献，这样 A(u, d - 1) 就会受到重复贡献。因此，对于 u，我们让 A(u, d) \backslash A(u, d - 1) 受到贡献，相当于令 f_{d, u} 加上 k。

我们对 u, v 路径上所有节点都执行这样的操作后，发现还有 A(x, d - 1) 和 x 子树外距离 x 不大于 d 的节点没有受到贡献。这部分是平凡的，容易转化为 \mathcal{O}(d) 次对 f 的单点加。

接下来考虑实现。查询为 \mathcal{O}(d) 次 f 的单点查，修改为 \mathcal{O}(1) 次 f_d 的链加和 \mathcal{O}(d) 次 f 的单点加。链加单点查拆成两条竖直链，每条直链再差分变成两条到根的链，据此转化为子树加单点求和，用树状数组维护。单点加对单点查的贡献容易统计。

综上，时间复杂度 \mathcal{O}((n + qd)\log n)。代码。