zoj 2912 Average distance

zoj 2912 Average distance

#include<cstring>#include<cstdio>#include<algorithm>#include<cstdlib>#define MAXN 10010using namespace std;struct Graph{    int next,vex,dis;};Graph g[MAXN<<1];int n,first[MAXN],ch[MAXN],a[MAXN],dis[MAXN],s[MAXN],pre[MAXN];bool visited[MAXN];void AddEdge(int v,int w,int d,int i){    g[i].dis=d;    g[i].vex=w;    g[i].next=first[v];    first[v]=i;}void DFS(int v){    int i,w;    visited[v]=true;    for(i=first[v];i!=-1;i=g[i].next)    {        w=g[i].vex;        if(!visited[w])        { ch[v]++; pre[w]=v; dis[w]=g[i].dis; DFS(w);        }    }}int  main(){    int t,i,j,k,v,w,d;    double ans;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        memset(visited,false,sizeof(visited));        memset(first,-1,sizeof(first));        memset(ch,0,sizeof(ch));        memset(a,0,sizeof(a));        for(i=j=0;j+1<n;j++)        { scanf("%d%d%d",&v,&w,&d); AddEdge(v,w,d,i);i++; AddEdge(w,v,d,i);i++;        }        DFS(0);        pre[0]=-1;        for(i=k=0,ans=0;i<n;i++) if(!ch[i])     s[k++]=i;        for(i=0;i<k;i++)        { v=s[i]; w=pre[v]; if(w==-1)     break; a[v]++; ans+=1.0*dis[v]*a[v]*(n-a[v]); a[w]+=a[v]; if(!(--ch[w]))     s[k++]=w;        }        printf("%lfn",ans*2/(n*(n-1)));    }    return 0;}