本文共 1603 字，大约阅读时间需要 5 分钟。

树结构中的每个边都被计算在多少对点之间的路径中，然后用边权乘以这些对数，求和即可得到总距离和。

树的每条边连接两个子树，左侧有a个节点，右侧有b个节点（a + b = n）。这些边会被a*b对点经过，因此其中权值w的总贡献是w * a * b。

总距离和即为所有边的w * a * b的总和。

最终，通过DFS遍历树，统计每条边分割后的子树大小，计算总和即可。

经过优化后的解释文章：

树结构中的每条边被多少对节点连接的路径经过，计算方法如下：

实现方法是深度优先搜索，每条边的子树大小统计后，计算每条边的贡献并求和。

代码改造后：

#include 
   
    #include 
    
     using namespace std;struct Edge {    int to, w;    Edge(int t, int w) : to(t), w(w) {}};vector
     
       children = {{-1}};ll dfs(int u, int parent) {    int sz = 1;    for (int v : children[u]) {        if (v == parent) continue;        sz++;        sz += dfs(v, u);    }    return sz;}void solve() {    int n = 3; // 定义树的节点数    vector
      
        adj = {{-1}, {0}, {1}}; // 1-2-3     // 填充相应的边信息    // 直接计算每条边的贡献 nums = sum(w_e * a * b)    // 这里通过遍历每个边，得到两边总节点数    int ans = 0;        return ans;}int main() {    solve();    return 0;}
      
     
    
   

代码简化为：

#include 
   
    #include 
    
     using namespace std;struct zuobiao {    int to, w;    zuobiao(int t, int w) : to(t), w(w) {}};vector
     
       children = {{-1}};ll dfs(int u, int parent) {    int sz = 1;    for (int v : children[u]) {        if (v == parent) continue;        sz++;        sz += dfs(v, u);    }    return sz;}void solve() {    int n = 3;    vector
      
       
        > adj = {{1, 2}, {2, 3}}; // 边信息    int ans = 0;    for (auto& edge : adj) {        int a = dfs(edge.second, -1);        int b = n - a;        ans += edge.first * a * b;    }    cout << ans; // 输出结果}int main() {    solve();    return 0;}
       
      
     
    
   

转载地址：http://wggjz.baihongyu.com/