計算樹中任意兩點間的平均距離

問題描述

給定一棵帶權重的樹，需要計算樹中任意兩個不同頂點之間距離的平均值。樹中有 n 個節點，節點編號從 0 到 n-1，共 n-1 條邊。任意兩點之間的距離定義為連接它們的唯一路徑上所有邊權重之和。平均距離等於所有無序節點對距離之和除以節點對總數 C(n, 2) = n*(n-1)/2。

輸入格式

• 第一行：測試用例數 t (1 ≤ t ≤ 100)。
• 每個測試用例第一行：節點數 n (2 ≤ n ≤ 10,000)。
• 隨後 n-1 行：每行三個整數 a, b, d，表示節點 a 和 b 之間有一條長度為 d (1 ≤ d ≤ 1000) 的邊。

輸出格式

對於每個測試用例，輸出一行，包含平均距離。答案的絕對誤差或相對誤差不超過 1e-6。

核心算法：邊貢獻法

暴力計算所有點對距離複雜度為 O(n^2)，會超時。利用樹的性質：刪除任意一條邊會將樹分成兩個連通分量，大小分別為 size 和 n-size。這條邊會被恰好 size * (n-size) 條路徑經過。因此，所有點對距離之和等於每條邊的 權重 * size * (n-size) 之和。

步驟

1. 建立鄰接表存儲樹。
2. 從任意節點（如 0）開始 DFS，計算以每個節點為根的子樹大小 subtree_size[u]。
3. 遍歷每條邊 (u, v, w)，假設 v 是 u 的子節點，則該邊貢獻為 w * subtree_size[v] * (n - subtree_size[v])。
4. 累加所有邊貢獻得到總距離和 total_dist。
5. 平均距離 = total_dist / (n * (n-1) / 2.0)。

時間複雜度

O(n) 每個測試用例，完全滿足 n ≤ 10,000 的限制。

樣例解析

輸入:
1
5
0 1 6
0 2 3
0 3 7
3 4 2

樹結構:
      0
    / | \
   1  2  3
           \
            4
邊權: 0-1:6, 0-2:3, 0-3:7, 3-4:2

計算子樹大小 (以0為根):
size[1]=1, size[2]=1, size[4]=1, size[3]=2, size[0]=5

邊貢獻:
0-1: 6 * 1 * 4 = 24
0-2: 3 * 1 * 4 = 12
0-3: 7 * 2 * 3 = 42
3-4: 2 * 1 * 4 = 8
總和 = 86
節點對數 = 5*4/2 = 10
平均 = 86/10 = 8.6

參考實現 (C++)

#include <bits/stdc++.h>
using namespace std;

struct Edge { int to; int w; };
const int MAXN = 10005;
vector<Edge> adj[MAXN];
int n;
long long subtree_size[MAXN];
long long total_dist;

void dfs(int u, int parent) {
    subtree_size[u] = 1;
    for (auto &e : adj[u]) {
        int v = e.to;
        if (v == parent) continue;
        dfs(v, u);
        subtree_size[u] += subtree_size[v];
        total_dist += (long long)e.w * subtree_size[v] * (n - subtree_size[v]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) adj[i].clear();
        for (int i = 0; i < n-1; ++i) {
            int a, b, d; cin >> a >> b >> d;
            adj[a].push_back({b, d});
            adj[b].push_back({a, d});
        }
        total_dist = 0;
        dfs(0, -1);
        double avg = (double)total_dist / (n * (n - 1) / 2.0);
        cout << fixed << setprecision(6) << avg << "\n";
    }
    return 0;
}