Warning: session_start(): open(/tmp/sess_dfcc1c1bd7df9ffe3057cde9eb9f3e90, 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)$ 求取每个点的树上最远点。

证明见 链接

或者可以考虑树形 $\text{dp}$,第一次 $\text{dfs}$ 维护每个节点子树方向上的最远距离和次远距离。

第二次 $\text{dfs}$ 维护每个节点祖先方向上的最远距离。

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