求树上结点的两两距离和——DFS求解

对于一棵N个结点的树，其N-1条边有各自的边权（长度），求树上所有结点两两之间的距离和， 即： $$\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}distance(i,j)$$

---

分析：

要求求 一棵N个结点的树 上 所有的任意两点之间的距离和；

那么 任意一条边对距离和的贡献 = 左端结点个数 * 右端结点个数 * 边权

和求重心类似，一次DFS即可，任选一个为根结点开始DFS；

对任意一条 边u -> v，右端结点个数 就是 向下遍历以v为根的子树的结点个数，那么 左端结点个数 就是 N - 右端点个数，相乘后再乘上边权即可。

int dfs(int u) //每次返回以u为根的子树的结点数量 { vis[u]=true; int sum=0; for(int i=head[u];i!=-1;i=e[i].next) { if(vis[e[i].v]) continue; int t=dfs(e[i].v); //u->v的右端结点个数，即以v为根的子树的结点个数 ans+=(N-t)*t*e[i].w; //ans+=左端*右端*边权 sum+=t; //统计 } return sum+1; //+1为结点u本身 } //ans即为最终答案