一句话理解
树上两点距离用 LCA。
为什么要学
dist=dep[x]+dep[y]-2*dep[lca]，无权。
讲解
有边权则用到根权值和。
例子
两段到 LCA 的路拼起来。
常见错误
- 边权不是 1 仍用 dep。
- lca 算错。
第 406 课
树上两点距离
🟠 进阶 约 10 分钟
练习 做完再看下一课
无权树距离可以用深度和 LCA 表示。
进度保存在本机浏览器里。
左右方向键也可翻课
第 406 课
树上两点距离用 LCA。
dist=dep[x]+dep[y]-2*dep[lca]，无权。
有边权则用到根权值和。
两段到 LCA 的路拼起来。
无权树距离可以用深度和 LCA 表示。
左右方向键也可翻课