树上距离

一句话理解

树上两点距离 = dep[x]+dep[y]-2*dep[LCA]。

为什么要学

有根后用 LCA。

讲解

边权为 1 时用深度；边权任意则用到根的带权距离。

例子

都走到 LCA，重的那段减掉两次。

常见错误

• 忘乘 2 减 LCA。
• 未预处理 LCA。