网站建设需求分析调研调查表,东莞市seo网络推广平台,西宁市精神文明建设网站,WordPress图片分类代码【HDU-2376】Average distance
题意#xff1a;
给你一个树#xff0c;求树上任意两个点之间的距离的平均值
题解#xff1a;
就是求出任意两点之间的距离和然后除以边数 ”任意两点之间的距离“ 和怎么算#xff1f; 我们去考虑边的贡献情况#xff1a; 对于边(u,v)
给你一个树求树上任意两个点之间的距离的平均值
题解
就是求出任意两点之间的距离和然后除以边数 ”任意两点之间的距离“ 和怎么算 我们去考虑边的贡献情况 对于边(u,v)u是v的父亲节点siz[v]表示以v为根的子树的节点数量(包含v)(n-siz[v]) 表示不在以v为根的子树的节点数量这两部分中各选一个点构成的连线都会经过(u,v)n是总节点,那么答案就是这个边的贡献就是ans(n-siz[v]) * siz[v] * w
代码
#includebits/stdc.h
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int MAXN 1e410;
int n;
vectorpairint,int e[MAXN];
LL dp[MAXN],sum[MAXN];void dfs(int cur,int father)
{sum[cur] 1;int len e[cur].size();for(int i 0; i len; i){int v e[cur][i].first;if(v father) continue;dfs(v,cur);sum[cur] sum[v];dp[cur] dp[v] sum[v]*(n-sum[v])*(e[cur][i].second);}return;
}int main()
{int T;scanf(%d,T);while(T--){scanf(%d,n);for(int i 0; i n; i){e[i].clear();dp[i] sum[i] 0;}int u,v,w;for(int i 0; i n-1; i){scanf(%d%d%d,u,v,w);e[u].push_back(make_pair(v,w));e[v].push_back(make_pair(u,w));}dfs(1,-1);printf(%.11f\n,(double)(dp[1]/(n*(n-1)/2.0)));}
}
