首页 > 巡逻
开通博客写题解
头像 DearFrozencodechenback
发表于 2019-08-16 14:45:08
k=1时，如果我们新修建一个道路，那么就会有一段路程少走一遍。此时选择连接树的直径的两个端点显然是最优的。 难就难在k=2的时候，还是上面的思路，先连接两个直径的端点。假设我们接下来连接的是x,y两个叶子结点，它们到直径的距离分别为dis[x],dis[y]，并设直径上两点的距离为d[u,v]，这里 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 louhc
发表于 2019-08-21 08:49:12
思路 当时,答案显然是树的直径减去新增的那条边.因为加上这条边,可以变成一棵基环树,那个环上的每条边只要走一编,其他边仍然要走两遍.当时,因为是两个环,要考虑这两个环是否相交.如果不相交,这两个环上的边都可以少走一遍.如果相交,这两个环共有的边仍然要走两遍(可以自行画图理解).这样就有一种做法,先找 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”