西北工业大学"编程之星"C题

王国

https://ac.nowcoder.com/acm/contest/5403/C

题目分析

由于出题人造数据的时候忘记造一种特殊数据,所以导致 可以水过.(也就是枚举边然后求距离) ,但是万幸的是ac的人中只有4个人是暴力的解法.

其中虚树和点分治占大多数

大约4,5个人使用了出题人的加法

点分治

此处省略1000字

虚树

此处省略1000字

出题人的解法

我们要在同一种颜色的点中,找到距离最远的两个点.

那么距离最远的两个点中,必然有一个点深度大的点. 所以我们找到这种颜色中深度最大的点,然后和其他求距离即可.(如果深度最大的点有多个,那么随便找一个就行)
正确性: 与两次dfs求树的直径本质上差不多

全部评论

相关推荐

11-20 17:40
西安邮电大学 有线传输工程师
点赞 评论 收藏
分享
11-23 12:16
武汉理工大学 电路设计工程师
点赞 评论 收藏
分享
头像
11-09 12:17
清华大学 C++
装杯可以判刑吗
out11Man：小丑罢了，不用理会
点赞 评论 收藏
分享
头像
10-16 12:29
携程_移动安全研发
转正了呀
Yushuu：你的确很厉害，但是有一个小问题：谁问你了？我的意思是，谁在意？我告诉你，根本没人问你，在我们之中0人问了你，我把所有问你的人都请来 party 了，到场人数是0个人，誰问你了？WHO ASKED？谁问汝矣？誰があなたに聞きましたか？누가 물어봤어？我爬上了珠穆朗玛峰也没找到谁问你了，我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒，在找到谁问你之前我连癌症的解药都发明了出来，我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆
点赞 评论 收藏
分享
11-18 23:50
北京科技大学 风电运维工程师
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
287005次浏览 2519人参与
# 学历or实习经历，哪个更重要 #
48968次浏览 378人参与
# 北方华创开奖 #
25237次浏览 274人参与
# 地方国企笔面经互助 #
3463次浏览 7人参与
# 美团求职进展汇总 #
1323226次浏览 12417人参与
# 选完offer后，你后悔学本专业吗 #
18324次浏览 131人参与
# 阿里云管培生offer #
4331次浏览 86人参与
# 如何一边实习一边秋招 #
990148次浏览 12628人参与
# 得物求职进展汇总 #
65540次浏览 677人参与
# 腾讯求职进展汇总 #
194808次浏览 1632人参与
# 银行笔面经互助 #
82114次浏览 872人参与
# 提前批简历挂麻了怎么办 #
145984次浏览 1942人参与
# 0offer是寒冬太冷还是我太菜 #
895438次浏览 7985人参与
# 海康威视求职进展汇总 #
397887次浏览 3403人参与
# 机械人，你在招聘流程中的企业有哪些？ #
17762次浏览 186人参与
# 许愿池 #
213186次浏览 2529人参与
# 国央企薪资爆料 #
5403次浏览 39人参与
# 网申一定要掌握的小技巧 #
5242次浏览 52人参与
# 你们公司几号发工资 #
10657次浏览 99人参与
# 没有实习经历，还有机会进大厂吗 #
810556次浏览 13915人参与
# 你最想要的公司福利是？ #
44658次浏览 179人参与
# 听到哪句话就代表面试稳了or挂了？ #
93717次浏览 785人参与
牛客网
牛客企业服务