[Codeforces 802L]Send the Fool Further! (hard)

Description

题库链接

给出一个 (n) 个节点的树。求从根节点出发，每次随机走一个相邻的点，问走到任意一个叶子节点经过的路径长度的期望。

(1leq nleq 10^5)

Solution

树上期望我们依旧用高斯消元来做。

设

[d(u)=sum_{ ext{v is the neighbor of u}} dist(u,v)]

其中 (dist(u,v)) 表示 ((u,v)) 间距离。设 (E(u)) 表示节点 (u) 到叶子节点的路劲长度的期望， (in_u) 为节点 (u) 的度数。容易得到方程

[E(u)=frac{E(fa_u)+sum E(son_u)+d(u)}{in_u}]

特别地对于叶子节点 (u) ， (E(u)=0) 。

可以用高斯消元来解，不过复杂度是 (O(n^3)) 的。考虑优化这个过程。

由于叶子节点的 (E=0) ，容易发现对于叶子节点的父亲，满足方程

[E(u)=frac{E(fa_u)+d(u)}{in_u}]

发现这个方程只有 (fa_u) 和 (u) 两个元，考虑将式子变形

[k_uE(u)=E(fa_u)+b_u]

其中 (k_u,b_u) 均为已知项。

我们可以考虑将这个线性相关的方程带入 (u) 的父亲。

[egin{aligned}E(fa_u)&=frac{E(fa_{fa_u})+sum E(son_{fa_u})+d(fa_u)}{in_{fa_u}}\&=frac{E(fa_{fa_u})+sum frac{E(fa_u)+b_{son_{fa_u}}}{k_{son_{fa_u}}}+d(fa_u)}{in_{fa_u}}end{aligned}]

发现这个方程也只有两个元，继续变形

[k_{fa_u}E(fa_u)=E(fa_{fa_u})+b_{fa_u}]

可以继续上代，发现最后的根节点没有父亲，得到的方程就会是

[k_{root}E(root)=b_{root}]

这样就可以做到 (O(n)) 求解了。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5, yzh = 1e9+7;

int n, k[N], b[N], fa[N], q[N], in[N], tail, u, v, c;
struct tt {int to, next; }edge[N<<1];
int path[N], top;

int quick_pow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b&1) ans = 1ll*ans*a%yzh;
        a = 1ll*a*a%yzh, b >>= 1;
    }
    return ans;
}
void dfs(int u) {
    q[++tail] = u;
    for (int i = path[u]; i; i = edge[i].next)
        if (edge[i].to != fa[u]) fa[edge[i].to] = u, dfs(edge[i].to);
}
void add(int u, int v) {edge[++top] = (tt){v, path[u]}, path[u] = top; }
void work() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &u, &v, &c); ++u, ++v;
        add(u, v), add(v, u); ++k[u], ++k[v], b[u] += c, b[v] += c;
    }
    for (int i = 1; i <= n; i++) in[i] = k[i];
    dfs(1);
    for (int i = n; i >= 1; i--)
        if (in[i] != 1) {
            int inv = quick_pow(k[i], yzh-2);
            (k[fa[i]] -= inv) %= yzh;
            (b[fa[i]] += 1ll*b[i]*inv%yzh) %= yzh;
        }
    printf("%d
", (1ll*b[1]*quick_pow(k[1], yzh-2)%yzh+yzh)%yzh);
}
int main() {work(); return 0; }