关于此题的口胡解法(错的)
查看原帖
关于此题的口胡解法(错的)
195044
2233颗GoldenEgg楼主2020/11/29 11:07

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

2020/11/29 11:07
加载中...