Warning: session_start(): open(/tmp/sess_9f751f0a91fb9e12f6d5120a27338fec, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:other:结论_1 [CVBB ACM Team]

用户工具

站点工具


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