文件名称：Pro 俩顶点之间的长度
文件大小：12.46MB
文件格式：RAR
更新时间：2023-05-11 11:18:35
算法
这道题第一眼看图，很多人可能认为是求任两点间最短距离，floyd,但是时间复杂度O(n^3)果断放弃 N个顶点N-1条边，之前遇见过类似的图形，知道肯定没有环，是棵树， 求树中多个两点间距离，实质求LCA(最近公共祖先)，（在之前Reference Book中有过论述，CCW在文中也有论述，希望大家有时间好好研读） 常用的是Tarjan 算法或者 倍增算法 或者DFS+ST算法 这道题结果输出所有问询距离总数，可采用了Tarjan离线算法（一次读入所有查询，统一处理），基于DFS和并查集（这两个知识点西安讲师在视频中讲过）， （根节点可以任选）在该过程中，维护一个所有节点到选定根的距离的数组 （u，v）两点间距离=u到根的距离+v到根的距离-2*LCA到根的距离
【文件预览】：
51Pro 俩顶点之间的长度 Distance between two vertices
----default.cpp(2KB)
----Pro 두 정점간의 길이.docx(52KB)
----sample_input.txt(14.1MB)
----Question_eng.txt(50KB)
----eval_output.txt(233B)
----Question_kor.txt(53KB)
----eval_input.txt(14.1MB)
----default_eng.cpp(2KB)
----参考答案（C++）.txt(2KB)
----sample_output.txt(233B)
----default_eng.java(1KB)
----grading.cpp(3KB)
----default.java(2KB)
----default.c(2KB)
----default_eng.c(1KB)
----Pro 俩顶点之间的长度.docx(53KB)