此题结论的另一种证明方法
查看原帖
此题结论的另一种证明方法
684254
Rain_chr楼主2024/9/23 22:17
  1. 路径必然经过树的中心

证明:树的中心是树中离其最远的点距离最小的点,其他的点在树中离其最远的点距离必然大于等于树的中心,所以树的中心必须被选中,不然答案会更大。

于是我们可以先将树的中心当作根,路径必然经过根。

  1. xx 为到根最远点,yy 为到根次远点,那么路径端点在 x,yx,y 到根路径上。

证明:如果路径不在x,yx,y 到根路径上。,那么答案必定为 x,yx,y 到根的距离,显然这样不优。

然后可以发现,到树的中心最远和次远的点就是直径的两个端点,于是我们绕了一大圈证明了直径包含路径,只不过限制更强而已(包含树的中心)。

2024/9/23 22:17
加载中...