hdu2376-Average distance（思维）

题目

原题链接

问题描述

给定一棵树，求任意两点之间距离的总和并计算其平均值。

分析

总共有$n$个点，也就是有$C_n^2$段，取出树上的一条边进行分析，考虑这条边对结果的贡献，也就是这条边总共会被使用几次。
假设边的权值为$val$，若边的左侧有$x$个点，右侧就有$n?x$个点，那么这条边通过排列组合对结果的贡献就是$x?(n?x)?val$。
那么我们就只要用一个$DFS$求每个节点子树（包括自己）的节点数，同时更新对应边对结果的贡献

易错点

我在写题时直接将边作为了有向边，以第一个值作为根节点的位置，实际上，应当将其理解为一个无向边，然后在$DFS$中记录父节点，以免重复遍历。
同时注意输出精度。

printf("%.6lf\n",ans);

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define fir(i, a, b) for (ll i = (a); i <= (b); i++)
#define rif(i, a, b) for (ll i = (a); i >= (b); i--)
const int N=1e4+5;
const  ll inf=1e9+10;
ll t,n,cnt[N];
vector<ll>son[N];
double sum[N];
double ans;
map<ll,map<ll,ll>>mp;
ll DFS(ll x,ll fa){
    cnt[x]=1;for(auto y:son[x]){
    if(y==fa)continue;ll tmp=DFS(y,x);cnt[x]+=tmp;ans+=tmp*mp[x][y]*(n-tmp)*2.0/(n*n-n);	}return cnt[x];
}
int main(){
    cin>>t;while(t--){
    cin>>n;ans=0;mp.clear();fir(i,0,n){
    son[i].clear();}ll x,y,z;fir(i,1,n-1){
    cin>>x>>y>>z;mp[x][y]=z;mp[y][x]=z;son[x].push_back(y);son[y].push_back(x);}DFS(0,-1);printf("%.6lf\n",ans);}return 0;
}