【每日一题】7月16日题目精讲—点权和


活动时间: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. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/25225cef2a314928bab6cf63afabc04e
点赞 回复
分享
发布于 2020-07-15 13:20
https://blog.nowcoder.net/n/ab157125173b4084b337a8e16621a238
点赞 回复
分享
发布于 2020-07-15 15:30
乐元素
校招火热招聘中
官网直投
https://blog.nowcoder.net/n/049907d918e04fdf906b51705a4018b8
点赞 回复
分享
发布于 2020-07-15 16:06
https://blog.nowcoder.net/n/b81d4409cce24306bdf196ee3460f854
点赞 回复
分享
发布于 2020-07-15 16:42
https://blog.nowcoder.net/n/5b90ed0fce764d7d8ef97bd83e401021
点赞 回复
分享
发布于 2020-07-15 22:13
https://blog.nowcoder.net/n/b7cf5e84587e419393f05336ddb0ea18
点赞 回复
分享
发布于 2020-07-15 23:39
https://blog.nowcoder.net/n/f7770e4681d74f4fb8e2450a272b7d7b
点赞 回复
分享
发布于 2020-07-16 14:11
https://blog.nowcoder.net/n/af9111a7667c42ef849541841cc1f541
点赞 回复
分享
发布于 2020-07-16 14:55
https://blog.nowcoder.net/n/3e8d7c29deca4211a1995529a68c0ffb
点赞 回复
分享
发布于 2020-07-16 16:10
https://blog.nowcoder.net/n/c709f70d94234afeae54a9963d06ce3b
点赞 回复
分享
发布于 2020-07-16 17:13
https://blog.nowcoder.net/n/691a97218c3942ecb4ac09fd35b55f42
点赞 回复
分享
发布于 2020-07-16 20:06
https://blog.nowcoder.net/n/9a3c3aae4adb4380b1dc335f40217c49
点赞 回复
分享
发布于 2020-07-16 20:59
https://blog.nowcoder.net/n/56382120d77d451e901404f1c2883371
点赞 回复
分享
发布于 2020-07-18 10:32
https://blog.nowcoder.net/n/741ffc4b12154c7bb9b1475713f1c264
点赞 回复
分享
发布于 2020-07-20 12:49
https://blog.nowcoder.net/n/71baf726e85b403ba8bc77c91c97bc84
点赞 回复
分享
发布于 2020-07-20 20:28
https://blog.nowcoder.net/n/9f4f7092059c47ce855f52fd63160ff3
点赞 回复
分享
发布于 2020-07-21 15:43
https://blog.nowcoder.net/n/68ea6d587e5b40e09b64cd11e68dc227
点赞 回复
分享
发布于 2020-07-21 22:18
https://blog.nowcoder.net/n/8b4ba063372b4a159d3ac81b91f2afa4
点赞 回复
分享
发布于 2020-08-06 01:09
https://blog.nowcoder.net/n/cf10144acee04ad89204db82ac0ea913
点赞 回复
分享
发布于 2020-08-16 09:19

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务