树中所有对最短路径之和

在树中，“所有节点对最短路径之和”的术语指的是计算所有节点对的个别最短路径的总和。一种有效的方法是使用双重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