Pro 俩顶点之间的长度

这道题第一眼看图，很多人可能认为是求任两点间最短距离，floyd,但是时间复杂度O(n^3)果断放弃 N个顶点N-1条边，之前遇见过类似的图形，知道肯定没有环，是棵树， 求树中多个两点间距离，实质求LCA(最近公共祖先)，（在之前Reference Book中有过论述，CCW在文中也有论述，希望大家有时间好好研读） 常用的是Tarjan 算法或者 倍增算法 或者DFS+ST算法 这道题结果输出所有问询距离总数，可采用了Tarjan离线算法（一次读入所有查询，统一处理），基于DFS和并查集（这两个知识点西安讲师在视频中讲过）， （根节点可以任选）在该过程中，维护一个所有节点到选定根的距离的数组 （u，v）两点间距离=u到根的距离+v到根的距离-2*LCA到根的距离