用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:other:结论_1

这是本文档旧的修订版!


结论

1、树上最远距离

树上到每个点距离最远的距离一定为树上一条直径的两个端点之一。

分别从两个端点开始 $\text{dfs}$ 即可 $O(n)$ 求取每个点的树上最远点。

证明见 树上直径相关证明

2020-2021/teams/legal_string/jxm2001/other/结论_1.1595689818.txt.gz · 最后更改: 2020/07/25 23:10 由 jxm2001