### 加权树中所有节点对间距离的高效计算 为了满足时间复杂度低于 \(O(N^2)\)，可以采用基于 **DFS 和动态规划** 的方法来解决此问题。这种方法的核心思想是利用树结构的特点，通过两次 DFS 遍历分别计算根到各节点的距离以及任意两点间的距离。 以下是具体的 Python 实现： #### 方法描述 1. 使用第一次 DFS 计算从某个选定根节点出发到达其他所有节点的距离。 2. 利用第二次 DFS 更新子树内部节点之间的距离总和。 3. 整体算法的时间复杂度为 \(O(N)\) 或接近线性级别。 #### 代码实现 ```python def calculate_all_pairs_distance(n, edges_with_weights): """ Calculate the sum of distances between all pairs of nodes in a weighted tree. :param n: Number of nodes in the tree. :param edges_with_weights: List of tuples representing edges and their weights [(u, v, w)]. :return: Sum of distances between all pairs of nodes. """ # Build adjacency list for the tree adj = [[] for _ in range(n)] for u, v, w in edges_with_weights: adj[u].append((v, w)) adj[v].append((u, w)) # Variables to store results during traversal subtree_size = [0] * n # Size of each node's subtree including itself dist_from_root = [0] * n # Distance from root to each node total_sum = [0] # Total sum of distances between all pairs def dfs1(node, parent): """First DFS to compute distance from root and size of subtrees.""" for neighbor, weight in adj[node]: if neighbor != parent: dist_from_root[neighbor] = dist_from_root[node] + weight dfs1(neighbor, node) subtree_size[node] += subtree_size[neighbor] subtree_size[node] += 1 def dfs2(node, parent): """Second DFS to re-root the tree at every child and update total sum.""" nonlocal total_sum for neighbor, weight in adj[node]: if neighbor != parent: # When moving from `node` to its child `neighbor`, adjust the total sum accordingly total_sum[0] += (subtree_size[neighbor] * (n - subtree_size[neighbor]) * weight) dfs2(neighbor, node) # Start first DFS assuming node 0 as root dfs1(0, -1) # Initialize total sum based on current root-to-node distances initial_total = sum(dist_from_root[i] for i in range(n)) total_sum[0] = initial_total # Perform second DFS to account for changes when re-rooting dfs2(0, -1) return total_sum[0] # Example usage if __name__ == "__main__": num_nodes = 5 edge_list = [ (0, 1, 3), (0, 2, 2), (1, 3, 1), (1, 4, 4) ] result = calculate_all_pairs_distance(num_nodes, edge_list) print(f"The sum of distances between all pairs of nodes is {result}.") ``` #### 解释 - 函数 `calculate_all_pairs_distance` 接收参数：节点数 `n` 和边列表及其权重 `edges_with_weights`。 - 构造邻接表表示加权无向图。 - 第一次 DFS (`dfs1`) 负责初始化每个节点与其父节点的距离，并统计其子树大小。 - 第二次 DFS (`dfs2`) 动态调整当重新选择不同节点作为根时的整体距离变化情况。 最终返回的是所有节点对之间距离之和的结果。 --- ### 性能分析 该算法的关键在于避免重复遍历整棵树多次。借助于 DFS 结合动态更新策略，在单次遍历过程中完成大部分必要的计算操作，从而达到近似线性的效率水平[^5]。