一道独立做出的紫题，感觉应该评绿到蓝。

题目翻译

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

题解

设 $f_u$ 表示从 $u$ 开始随机游走的期望步数。
$$f_u = \frac{f_{fa_{u}} + w_{u,fa_{u}} + (\sum\limits_{v \in son_{u}} f_v + w_{u,v})}{deg_u}$$

设 $sumw_u$ 表示 $u$ 的所有邻居的边权和。

$$f_u = \frac{f_{fa_{u}} + (\sum\limits_{v \in son_{u}} f_v) + sumw_u}{deg_u}$$

然后发现这个方程包含自己，所以可以直接高斯消元 $O(n^3)$ 干下去。
但是这复杂度不优，并且我也不会写高斯消元。
我们不希望在计算一个节点的时候，要先计算它父节点和所有子节点的信息，所以考虑一种常规套路。
设 $f_u = k_u \times f_{fa_u} + b_u$

带入方程式，得：

$$f_u = \frac{f_{fa_{u}} + (\sum\limits_{v \in son_{u}} k_v \times f_u + b_v) + sumw_u}{deg_u}$$

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

$$f_u = \frac{f_{fa_{u}} + sumk_u \times f_u + sumb_u + sumw_u}{deg_u}$$

尝试把它化成 $f_{u} = k_u \times f_{fa_u} + b_u$ 的形式。
化简后变成这样（学过小学数学的都会）：

$$f_u = \frac{1}{deg_u - sumk_u} \times f_{fa_u} + \frac{sumb_u + sumw_u}{deg_u - sumk_u}$$

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

由于根节点没有父节点，所以它的 $f$ 相当于 $b$。
叶节点出师未捷身先死，所以 $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;
}