最近刚学了树的中心,所以看到这个题目里提到的中心特别敏感
以下是我的口胡:
因为这棵树的边权都是正数,所以中心一定在某一条直径上,而根据https://www.codetd.com/article/7651409
这位大佬的证明,在任意一条直径上求最小偏心距都是等价的,所以只要在一条直径上找最优就行了
根据树的中心的定义:中心到其他点的最大距离最小,而离中心最远的点又一定是直径的端点,所以最终答案不就是中心到其他的点的最大距离了吗?
(如果我们选的路径不包含中心,那么这条路径上的每一个点都没有中心更优,而如果我们选的路径包含了中心,那么中心一定是其中最优的)
但是这个想法连样例都过不了,求大佬解释哪里错了