题解：P11287 [COTS 2017] 影响 Utjecaj

EityDawn · 2024-11-20 11:58:21 · 题解

思路：

注：分析默认 n，m，q 同阶。

假设从图中删去关键节点，那么图将被划分成若干个联通块。如果有关键点与联通块相连，那么这个联通块内的点都是可达的。

所以考虑将联通块打包，缩成一个点，断开关键节点之间的边。

那么一个点的影响力就是所有与之直接相连的点和自身的权值之和。

那么问题转化为了：

1. 对点 x 和直接相连的点加上一个值。
2. 查询点 x 和直接相连的点的权值和。

直接做是 O(n\sum deg_i)，deg_i 是点 i 的出度。

考虑根号分治。我们设立一个阈值 B，初始时先将点 x 和直接相连的点的权值和预处理出来。对于修改操作，若 deg_x\le B，直接暴力修改，反之，我们对 x 打上标记。询问时，我们再在权值和的基础加上与 x 相连的且出度 >B 的点上的标记。修改操作是 O(B)，而对于询问，默认 \sum deg_i \le 2\times n，那么出度 > B 的点不超过 {n}\over B，询问复杂度为 O({n\over B})。