下午写的东西被奇妙地吞掉了ovo
最小直径生成树,一定不要用sort,否则会tle.
首先考虑一个绝对中心的概念.既在生成树上它是所有直径的严格中心.它有可能在点上,也有可能在边上.
于是我们枚举边,试图让这个绝对中心在这条边上.那么每个点都选择到这条边的最短路树来生成.如果两个端点的最长链的差距不是很大,那么就有可能在这条边上找到最小直径生成树的绝对中心.
考虑绝对中心对一个端点的距离,会对每个点形成一个峰形的函数.要找的答案就在相邻两个峰之间.于是可以利用两边直线k相同,把b排序之后直接做.总复杂度O(n3).
然后如果每个边强行排序只会多个log,但是会tle.