(封面图与内容完全无关，只是因为图好看才放上来)

这次打算把HDU3276和HDU5723两道题放在一起讲，主要是因为这两道题都涉及到了求树上任意两点的距离的总和；HDU5723除此之外还多了一点就是求最小生成树。不过讲真，个人认为其实HDU5723将对这两者融合得并不好，求最小生成树以及求距离和这两个之间的联系有点牵强......emmmmmm，毕竟只是签到题？

先说HDU3276

直接枚举每一个点对然后对点对dfs肯定是行不通的，所以我们可以这么考虑：对于一条边而言，它对于距离总和的“贡献”，即为它被走过的次数乘以它的长度。而它被走过的次数，就是它符合这样的条件的点对的个数：一个点在这条边的一侧，另一个点在这条边的另一侧。由此即可求出这条边的贡献。总的距离之和即为所有边的贡献的总和。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e4+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct edge{
    int to;
    ll wei;
};
vector<edge> gra[maxn];
double ans=0;
int n;
ll sum[maxn];
void dfs(int rt,int fa)
{
    sum[rt]=1;
    for(int i=0;i<gra[rt].size();i++){
        int son=gra[rt][i].to;
        if(son==fa)        continue;
        edge& e=gra[rt][i];
        dfs(son,rt);
        sum[rt]+=sum[son];
        ans+=sum[son]*((ll)n-sum[son])*e.wei;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ans=0;memset(sum,0,sizeof(sum));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            gra[i].clear();        //记得清空，否则可能mle
        for(int i=1;i<n;i++){
            int a,b;ll d;
            scanf("%d %d %lld",&a,&b,&d);
            gra[a].push_back(edge{b,d});
            gra[b].push_back(edge{a,d});
        }
        dfs(0,-1);
        double tot=ans/(((double)(n-1)*(double)n)/2);
        printf("%.6lf\n",tot);
    }
    return 0;
}

<p>注意题目中的精度是10<sup>-6</sup>!所以要%.6lf!另外因为这题是spj，所以虽然看起来样例没过，其实没关系</p>

然后是HDU5723

其实只是在上面题目的基础上多了个求最小生成树，kruskal求一下即可。

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m; 
int pre[maxn];
struct edge{
    int from;
    int to;
    ll wei;
};
vector<int> tree[maxn];
edge arr[maxn*10];
ll sum[maxn];
ll ans; 
bool cmp(edge a,edge b)
{
    return a.wei<b.wei;
}
void init()
{
    for(int i=1;i<=n;i++)
        pre[i]=i;
}
int findr(int x)
{
    if(pre[x]==x)
        return pre[x];
    return pre[x]=findr(pre[x]);
}
ll kruskal()
{
    ll rsl=0;
    int num=0;
    init();
    for(int i=1;i<=m;i++)
    {
        int fx=findr(arr[i].from);
        int fy=findr(arr[i].to);
        if(fx!=fy)
        {
            pre[fx]=fy;
            rsl+=arr[i].wei;
            num++;
            tree[arr[i].from].push_back(i);
            tree[arr[i].to].push_back(i); 
        }
    }
    if(num==n-1)
        return rsl;
    else
        return 0;
}
/*
exp=1/(n*(n-1))*(tot_len*2)
*/
void dfs(int rt,int fa)
{
    sum[rt]=1;
    for(int i=0;i<tree[rt].size();i++){
        int& idx=tree[rt][i];        //tree数组中存的是边的编号 
        int son;
        if(rt==arr[idx].from)
            son=arr[idx].to;
        if(rt==arr[idx].to)
            son=arr[idx].from;
        if(son==fa)        continue;
        dfs(son,rt);
        sum[rt]+=sum[son];
        ans+=(ll)((sum[son]*((ll)n-sum[son]))*(arr[idx].wei));
    }
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        ans=0;
        memset(sum,0,sizeof(sum));
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)        tree[i].clear();
        for(int i=1;i<=m;i++){
            int x,y;ll w;
            scanf("%d %d %lld",&x,&y,&w);
            arr[i]=edge{x,y,w};
        }    
        sort(arr+1,arr+m+1,cmp);
        ll min_cost=kruskal();
        dfs(1,-1);
        double exp=(double)ans*(2/((double)n*(double)(n-1)));
        printf("%lld %.2lf\n",min_cost,exp);
    }
    return 0;
} 

<p>tree存的是边在arr中的编号</p>