活动时间：7月7日起至9月1日
活动内容：写满30篇每日一题的题解
活动奖励：即可额外获得牛客T恤一件
活动目的：滴滴滴～想充实的过完这个暑假嘛～快来写每日一题～每天都要进步喔～提升自己的同时还有超多福利喔～

每日一题交流群，群内定期有福利发放，群号：659028468

7月16日题目
题号 NC14393
名称 点权和
来源 牛客练习赛6
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

每次修改一个点时，会被更新的是它自己、它父亲、它儿子，如果我们用一个数组来存每个点周围的个点的和，那么一个点的修改造成影响的除了自己、父亲、儿子之外还有“祖父”，“孙子”，“兄弟”——对于它自己，修改了多少个点就需要加几；对于父亲和儿子，相邻点权值和+2；对于祖父、孙子、兄弟，相邻点权值和+1。
对每个点维护三个标记：
f1[x] 点x自己+1的次数
f2[x] x的儿子+1的次数
f3[x] x的孙子+1的次数
显然每次修改x之后总数为：
父亲节点fa[x]的值为：它自己加一次数+它儿子加一的次数+它的父亲加一的次数，即：
它自己x的值：它自己加一次数+它儿子加一的次数+它的父亲加一的次数，即
它孩子yi的贡献：孩子个数*它加一的次数+它儿子加一的次数+它孙子+1的次数，即
我们在每次修改的时候网上维护到“祖父”即可把f1,f2,f3维护出来。

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目7月23日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴