P4281 [AHOI2008] 紧急集合 / 聚会 推导
__ryp__
·
·
个人记录
设三个点为 a, b, c，x =\text{lca}(a, b), y = \text{lca}(b, c), z = \text{lca}(a, c)，不妨设 x = y，那么总距离为：
d(a) - d(x) + d(b) + d(c) - 2 \times d(z) + d(z) - d(x)
整理得
d(a) + d(b) + d(c) - 2\times d(x) - d(z)
也即
d(a) + d(b) + d(c) - d(x) - d(y) - d(z)