题目翻译

求从 0 号节点开始随机游走，到叶子节点停止的期望步数。

题解

设 f_{u} 表示从 u 开始随机游走的期望步数。

设 sumw_{u} 表示 u 的所有邻居的边权和。

然后发现这个方程包含自己，所以可以直接高斯消元 O(n^3) 干下去。

但是这复杂度不优，并且我也不会写高斯消元。

我们不希望在计算一个节点的时候，要先计算它父节点和所有子节点的信息，所以考虑一种常规套路。 设 f_{u} = k_{u} × f_{f_{a_u}} + b_u

带入方程式，得：

设 sumk_u , sumb_u 表示 u 的所有儿子的 k_v,b_v 之和。

尝试把它化成 f_u = k_u × f_{f_{a_u}} + b_u 的形式。

化简后变成这样（学过小学数学的都会）：

这样计算一个节点的时候不需要先计算它的父节点信息了，所以递归下去算 k_u,b_u 即可。

由于根节点没有父节点，所以它的 f 叶节点出师未捷身先死，所以 k,b = 0。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, M = N << 1, mod = 1e9 + 7;
int n, h[N], e[M], w[M], ne[M], idx = 0;
int deg[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

int k[N], b[N];
void dfs(int u, int father) {
    if (deg[u] == 1 && u != 1) {
        k[u] = 0, b[u] = 0;
        return;
    }
    int sumw = 0, sumk = 0, sumb = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        (sumw += w[i]) %= mod;
        if (v == father) continue;
        dfs(v, u);
        (sumk += k[v]) %= mod, (sumb += b[v]) %= mod;
    }
    int inv = qmi((deg[u] - sumk + mod) % mod, mod - 2);
    // cout << u << ' ' << sumb << ' ' << sumw << ' ' << deg[u] - sumk << endl;
    k[u] = inv, b[u] = (sumb + sumw) * 1ll * inv % mod;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) h[i] = -1;
    for (int i = 1, a, b, c; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        a++, b++;
        deg[a]++, deg[b]++;
        add(a, b, c), add(b, a, c);
    }
    dfs(1, 0);
    // for (int i = 1; i <= n; i++) cout << i << ' ' << k[i] << ' ' << b[i] << endl;
    printf("%d\n", b[1]);
    return 0;
}