关于思路

P2491 [SDOI2011] 消防

@[_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


|