树上两点距离的 O(n)-O(1) 做法

Dynamic_Elaina · 2026-03-03 15:12:27 · 休闲·娱乐

目标是求解点 A 和点 B 在树上的距离，我们指定树的根为点 O，这样就转换成了有根树，有根树我们可以连从父亲到儿子节点的有向边，变成一棵有向树。

根据高中数学知识，有向边和向量都是个箭头，所以是等价的。原问题转换为求 |\overrightarrow{AB}|，DFS 跑一遍对每个点进行向量加法得出 \overrightarrow{OA}、\overrightarrow{OB}，预处理是 O(n) 的。查询向量减法 O(1) 即可得出答案。