I_love_Vae @ 2024-11-16 21:29:10
给定一棵树，计算树中两个顶点之间的平均距离。比如下面这棵树中两个顶点的平均距离是：
图片
第一行带有整数n(2<=n<=100000)表示树中的节点数，节点编号从1到n。接下来n-1行，每行包含三个整数x,y,z(1 <= z <= 10000)表示x和y节点之间有距离为z的条边，数据保证是一棵树。
输出一行，表示平均距离，精确到小数点后6位数(四舍五入)。
5
1 2 6
1 3 3
1 4 7
4 5 2
8.600000
10000 1<=z<=10000$
by I_love_Vae @ 2024-11-16 21:34:02
应该是树形DP，但我自己的代码没调AC，求dalao帮忙改/重写一下 我的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int sum[N], n;
ll dp[N];
struct VAE
{
int v, w;
};
vector<VAE> g[N];
void dfs(int u, int fa)
{
sum[u] = 1;
for(int i = 0; i < g[u].size(); i ++)
{
int v = g[u][i].v;
if(fa == v)
{
continue;
}
dfs(v, u);
sum[u] += sum[v];
dp[u] += dp[v] + (n - sum[v]) * sum[v] * g[u][i].w;
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n - 1; i ++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(0, -1);
printf("%f", dp[0] * 2.0 / n / (n - 1));
return 0;
}by I_love_Vae @ 2024-11-16 22:12:39
@I_love_Vae
我是乐子没读题根节点是1，而且不开long long 见祖宗