@[_fairytale_](/user/280999)
首先设直径左右端点为 $u,v$,则对于任意点 $x$ ,$\max(dist(x,u),dist(x,v))=\max_{i=1}^ndist(x,i)$,翻译成人话就是直径端点之一是离 $x$ 最远的点。
如果枢纽至少有一个点在直径上,设枢纽在直径上最左侧、最右侧的点是 $x,y$,则 $x$ 左边离 $x$ 最远的点是 $u$(否则可以用更远的点替代 $u$ 作为直径),枢纽不走直径就无法降低最大距离。右侧同理。
否则(枢纽没有点在直径上)设枢纽上 $\max(dist(x,u),dist(x,v))$ 最小的点为 $w$,将 $w$ 向直径方向移动。此时我们只需证明 $\max(dist(w,u),dist(w,v))$ 即为当前答案,就可以说明其它点没有影响,且将 $w$ 向直径方向移动会减小答案。考虑以 $w$ 最终移到直径上时所在的点(记为 $r$)作为根,则 $w$ 子树内没有一对点的距离比 $\max(dist(w,u),dist(w,v))$ 大。若有这样的一对点 $p,q$,则 $\max(dist(w,u),dist(w,v))\geq\max(dist(r,u),dist(r,v))\geq \frac{1}{2}dist(u,v)$,同理 $\max(dist(w,p),dist(w,q))\geq\frac{1}{2}dist(p,q)$,将 $w$ 子树内外的两段拼起来,长度为 $\max(dist(w,u),dist(w,v))+\max(dist(w,p),dist(w,q))\geq\frac{1}{2}(dist(u,v)+dist(p,q))>dist(u,v)$,比直径大,矛盾。
by whdywjd @ 2024-02-15 13:01:05
@[whdywjd](/user/315448) 有点晕,但是 thx!有没有图之类的/kel
by _fairytale_ @ 2024-02-15 21:36:08
```
##** *
***** # **
* #* # **
* # # *
s-----------x#######y-----------t
```
`#` 是枢纽,`-` 是直径。
由于 x 到 s 的距离更长,y 到 t 的距离更长,把 x 左侧的链和 y 右侧的链移到直径上会更优:
```
**** *
***** * **
* ** * **
* * * *
s------#####x#######y##---------t
```
by whdywjd @ 2024-02-16 10:57:38
@[_fairytale_](/user/280999)
如果枢纽与直径无交,则移到直径上会更优。
```
###* *
***** # **
* ## * **
* * * *
s-------------------------------t
```
等价于:
```
**** *
***** * **
* #* * **
* * * *
s-------------------------------t
```
(只保留了离直径最近的点)
移到直径上更优:
```
**** *
***** * **
* ** * **
* * * *
s-----------#-------------------t
```
by whdywjd @ 2024-02-16 11:01:15
@[whdywjd](/user/315448) thx!
by _fairytale_ @ 2024-02-16 11:11:58