AcWing
首页
课程
题库
更多
竞赛
题解
分享
问答
应用
历史记录
清除记录
猜你想搜
AcWing热点
App
登录/注册
AcWing 5560. 树的直径
原题链接
困难
作者:
Chosen1.
, 2024-03-25 01:38:47 , 所有人可见 , 阅读 20
1
分类讨论下这个问题
首先确定的是原来的树存在一个直径,我们暂且设直径的两个端点是A和B
一个操作后在,我们在u点下新增了x,y点
如果产生了新的直径,那么必然是x,y是新的端点
根据我们的知识来看,已经产生了新的直径的话:
我们选一个点进行搜最长边,不如我们就选原来直径的A端点
可能会搜到我们的新端点x或者y,那么a-x一定是新的直径
还是搜到原来的最长边b,我们再从b搜,也一定会搜到x,如果又重新搜回a了,证明我们的直径没有变化
0 评论
提交评论
你确定删除吗?
AcWing
请输入登录信息
记住我
请输入绑定的邮箱地址
请输入注册信息