60 字
1 分钟
与树相关

树的直径#

树的直径必须边#

对于任意一条直径 a0,a1,⋯ ,aka_0,a_1,\cdots,a_k ,假设找到最大的 leftleft alefta_{left} 可以替换 a0,a1,⋯ ,alefta_0,a_1,\cdots,a_{left} 的部分,最小的 rightright arighta_{right} 可以替换 aright,⋯ ,aka_{right},\cdots,a_k 部分,那么 right−leftright - left 就是必须边