在树中，“所有节点对最短路径之和”的术语指的是计算所有节点对的个别最短路径的总和。一种有效的方法是使用双重DFS（深度优先搜索）算法。在第一次DFS遍历期间确定所选节点与每个其他节点之间的距离。在第二次DFS遍历期间再次遍历树，将每个节点视为潜在的LCA（最低公共祖先），并计算所选LCA的后代节点对之间的距离之和。使用这种方法可以计算出树中所有节点对最短路径之和，并确保得到一个理想的解决方案
使用的方法
-
双重 DFS（深度优先搜索）方法
-
动态规划方法
双重 DFS（深度优先搜索）方法
对于树中所有对最短路径的总和，我们使用双重 DFS（深度优先搜索）方法，该方法涉及两次 DFS 遍历。首先，我们计算从任何节点开始到所有其他节点的距离。然后，在第二次 DFS 遍历期间，我们导航树，同时将每个节点视为潜在的 LCA。我们在遍历时计算并求和作为所选 LCA 后代的节点对之间的距离。通过对所有节点重复此过程，我们获得所有对最短路径的总和。该策略对于这个问题非常引人注目，因为它有效地计算了树中所有节点集之间的距离总和。
算法
-
树中的任何节点都可以作为起始节点
-
为了确定从选择的起始节点到所有其他节点的距离，从该节点开始执行深度优先搜索（DFS）。这些距离应该保存在一个数组或数据结构中。
-
接下来，在树上运行第二次深度优先搜索（DFS），将每个节点视为可能的最近公共祖先（LCA）
-
在第二次 DFS 期间遍历树时，计算作为所选 LCA 后代的节点对之间的距离。对于每个 LCA，将这些距离加在一起。
-
对树中的每个节点重复此过程
-
树中最有限方式的所有匹配的总和由步骤 4 中所有计算距离的总和表示。
Example
的中文翻译为：
示例
#include
#include
using namespace std;
const int MAXN = 10005;
vector graph[MAXN];
int ancestor[MAXN];
int dfs(int node, int lca, int distance) {
int sum = 0;
for (int neighbor : graph[node]) {
if (neighbor != lca) {
sum += dfs(neighbor, lca, distance + 1);
}
}
return sum + distance;
}
int main() {
int lca_node = 0;
int total_sum = 0;
for (int node = 0; node val + 1, 0);
dfs(root, distances);
int total_sum = 0;
for (int distance : distances) {
total_sum += distance;
}
return total_sum;
}
int main() {
TreeNode* root = new TreeNode{0};
int result = sumOfAllPairShortestPaths(root);
cout
