题目描述：
我们建造了一个大项目！这个项目有n个节点，用很多边连接起来，并且这个项目是连通的！
两个节点间可能有多条边，不过一条边的两端必然是不同的节点。
每个节点都有一个能量值。
现在我们要编写一个项目管理软件，这个软件呢有两个操作：
1.给某个项目的能量值加上一个特定值。
2.询问跟一个项目相邻的项目的能量值之和。（如果有多条边就算多次，比如a和b有2条边，那么询问a的时候b的权值算2次）。
题解：
对于每个查询的答案，有两种获得答案的方式：
- 更新时单点更新点权val，查询时点x的答案为相邻点的val和，这种方式更新O(1)，查询O(n)
- 更新时除了更新点权val，同时还更新周围点的答案ans，查询时直接输出答案，这种方式更新O(n)，查询O(1)
均摊复杂度的思想：上面两种操作复杂度都不行,不管采用哪种，最坏复杂度都会达到O(n*m)。考虑以根 m为界限划分两种操作。对于一个点，如果这个点的度d sqrt(m)，那么我们希望通过更新时预处理的方式使得答案可以直接输出而不用遍历邻接点。对于更新时预处理：如果一个点的d sqrt(m) 怎么整p>
对于d > sqrt(m) 的情况，他的邻接点分两种，一种是 d sqrt(m)，就需要更新。
把复杂度降下来需要删边，将点分为重点和轻点，重点是度数 > sqrt(m)的点，轻点是度数
有没有可能一条边都删不掉，完全图就是，但这种图点数只有sqrt(m)个，符合复杂度要求。
边越多，点就越少。
代码
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！