louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共2篇）

题解 | 算法竞赛进阶指南树网的核

思路通过大胆猜想与小心伪证,我们可以得到一个结论: 在任何一条直径求得的最小偏心距都是相等的. 有了这个结论,我们就可以乱搞啦.对于直径,若选取的核为,最小偏心距只有可能为,,或者是选取整条直径为核时的最小偏心距.(十分好证)那么先求出某条直径的最小偏心距,然后在直径两端分别为虎一个指针,不断...

树的直径

2019-08-23

0 733

题解 | 算法竞赛进阶指南巡逻

思路当时,答案显然是树的直径减去新增的那条边.因为加上这条边,可以变成一棵基环树,那个环上的每条边只要走一编,其他边仍然要走两遍.当时,因为是两个环,要考虑这两个环是否相交.如果不相交,这两个环上的边都可以少走一遍.如果相交,这两个环共有的边仍然要走两遍(可以自行画图理解).这样就有一种做法,先找...

树的直径

2019-08-21

0 659