如何计算加权无向树中所有顶点对的总距离？C++实现求推荐

核心思路：计算每条边的贡献 #

树的特性是任意两点间路径唯一，所以每条边对总距离的贡献 = 边权 × 该边被跨越的顶点对数量。

具体来说，当你把一条边从树中移除，树会被分成两个独立的子树，假设它们的顶点数分别是s和n-s，那么这条边会被s*(n-s)对顶点跨越（左边每个点到右边每个点的路径都必须经过这条边）。把所有边的贡献相加，就是所有顶点对的距离总和。

这种方法的时间复杂度是O(n)，远优于多源Dijkstra/DFS的O(n²)，适合处理大规模顶点的情况。

C++实现示例 #

用邻接表存储树，通过DFS遍历计算子树大小，同时累加每条边的贡献：

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
vector<vector<pair<int, int>>> adj; // 邻接表：adj[u]存储(邻接顶点v, 边权w)
ll total = 0;
int n;

// 返回以u为根的子树的顶点数量，同时计算边的贡献
int dfs(int u, int parent) {
    int size = 1;
    for (auto &edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v != parent) {
            int child_size = dfs(v, u);
            total += (ll)w * child_size * (n - child_size);
            size += child_size;
        }
    }
    return size;
}

int main() {
    cin >> n;
    adj.resize(n + 1); // 假设顶点编号从1到n
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    dfs(1, -1); // 任选一个根节点，比如1
    cout << total << endl;
    return 0;
}

为什么之前的方法效率低？ #

• Dijkstra算法：是单源最短路算法，若对每个顶点都跑一遍，时间复杂度为O(n(n log n))，当n较大（比如1e4以上）时会超时。
• Prim算法：用于求解最小生成树，和计算顶点对距离总和的问题无关，自然解决不了。
• 多源DFS：每个顶点都做一次DFS计算到其他点的距离，时间复杂度也是O(n²)，同样不适合大规模数据。

验证示例 #

以你提到的4顶点树（a-b、a-c、c-d，假设边权都为1）：

• 边a-b：分割成大小1和3，贡献1×1×3=3
• 边a-c：分割成大小2和2，贡献1×2×2=4
• 边c-d：分割成大小1和3，贡献1×1×3=3
  总距离和=3+4+3=10，手动计算所有点对：
  a-b(1)、a-c(1)、a-d(2)、b-c(2)、b-d(3)、c-d(1)，总和1+1+2+2+3+1=10，结果一致。

内容的提问来源于stack exchange，提问作者KACPERKACPER