240331米哈游笔试第三题

题目:给你一颗树,n个节点,边长为1,求任意两点的路径和。u, v 和 v, u 算同一条路径,故只算一次。(已经简化了,本来是还有一些边长为0,可以把0的点缩掉)

先以节点1为起点,计算1到各个点的路径和。

1-3, 1-2, 1-4, 1-5 = 8

然后换根,进行dfs,向子树移动

移动到 3 节点时,增量 = - (目标子树 - 1) + (n - 目标子树 - 1) = n - 2 * 目标子树

例如:从 1 -> 3 时,8 + (5 - 4 * 2)= 5

3-1, 3-2, 3-4, 3-5 = 1 + 1 + 1 + 2 = 5

例如:从 3 -> 4 时,5 + (5 - 2 * 2)= 6

4-1, 4-2, 4-3, 4-5 = 2 + 2 + 1 + 1 = 6

例如:从 3 -> 2 时,5 + (5 - 1 * 2)= 8

例如:从 4 -> 5 时,6 + (5 - 1 * 2)= 9

最终,每条边被计算两次,所以最终答案/2

result = (8 + 5 + 6 + 8 + 9) / 2 =18

全部评论
请问一下增量公式是怎么推出来的
点赞 回复 分享
发布于 2024-04-02 09:30 广东
不懂就问,为什么3为目标的时候子树是4,不是3
点赞 回复 分享
发布于 2024-04-01 11:01 福建

相关推荐

不愿透露姓名的神秘牛友
今天 14:22
点赞 评论 收藏
分享
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务