网站建站描述撰写,单页网站排名优化,网络热词2022流行语及解释,西安网站公司排名HDU_2376 对于任意一棵子树来讲#xff0c;以根节点为深度最浅的点的路径一共有两类#xff0c;一类是以根节点为端点的路径#xff0c;另一类是过根节点但端点分别在两棵子树中的路径。然后将无根树转化为有根树后dfs时计算出上面两类路径的长度即可。 #includestdio.h…HDU_2376 对于任意一棵子树来讲以根节点为深度最浅的点的路径一共有两类一类是以根节点为端点的路径另一类是过根节点但端点分别在两棵子树中的路径。然后将无根树转化为有根树后dfs时计算出上面两类路径的长度即可。 #includestdio.h
#includestring.h
#includealgorithm
#includequeue
#define MAXD 10010
#define MAXM 20010
typedef long long LL;
LL f[MAXD], ANS;
int N, first[MAXD], size[MAXD], e, next[MAXM], v[MAXM], w[MAXM];
void add(int x, int y, int z)
{v[e] y, w[e] z;next[e] first[x], first[x] e ;
}
void init()
{int i, x, y, z;scanf(%d, N);memset(first, -1, sizeof(first[0]) * N), e 0;for(i 1; i N; i ){scanf(%d%d%d, x, y, z);add(x, y, z), add(y, x, z);}
}
struct St
{LL f;int size;St(){}St(LL _f, int _size) : f(_f), size(_size){}
};
void dfs(int cur, int fa)
{int i, s 0;LL A 0;size[cur] 1, f[cur] 0;std::queue St q;for(i first[cur]; i ! -1; i next[i])if(v[i] ! fa){dfs(v[i], cur);size[cur] size[v[i]], f[cur] f[v[i]] w[i] * size[v[i]];q.push(St(f[v[i]] size[v[i]] * w[i], size[v[i]]));}ANS f[cur];while(!q.empty()){St st q.front();q.pop();ANS st.size * A s * st.f;s st.size, A st.f;}
}
void solve()
{ANS 0;dfs(0, -1);printf(%.7f\n, (double)ANS * 2 / (N * (N - 1)));
}
int main()
{int t;scanf(%d, t);while(t --){init();solve();}return 0;
}
