题意

给你一颗树
从1号点开始随机游走
如果走到叶子就停下来
问你期望步数

前言

CQzhangyu在pkuwc提到的一个题啊，现在赶紧来做一做
当时太弱了，连高斯消元解期望都不会，更别提这个了
但是如今，我已经会这个啦

题解

引用CQzhangyu的吧，但也有不同（我做了一点点修改）

很自然想到游走那题，于是想到高斯消元，但是正常高斯消元是$O(n^3)$的。不过我们有一个套路：在树上进行高斯消元的复杂度是$O(nlogn)$的。log是求逆元的log
先列出方程：设f(x)表示从x开始期望还要走的路程，x的度数是d，那么$f(x)=\frac {f(fa)+len} d+\frac {\sum f(ch)+len} d$。而在叶子处，方程是形如$f(x)=k(fa)+b）$的，将其代入父亲的方程，便可以使父亲的方程也变成$f(x)=k（f(fa)+b）$的形式，这样一路消上去，就得到了根节点的答案了。

为了保存方便，我们对于k，保存他的倒数形式就可以了
至于怎么转移，推推式子就可以了，很简单的
然后如果你想知道全部地
就先消到1号点，再从1号点消下来就可以了
CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const LL N=100005*2;
LL n;
struct qq {LL x,y,z,last; }e[N];LL num,last[N];
LL k[N],b[N],f[N];
int d[N];
void init (LL x,LL y,LL z)
{num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
LL pow (LL x,LL y)
{if (y==1) return x;LL lalal=pow(x,y>>1);lalal=lalal*lalal%MOD;if (y&1) lalal=lalal*x%MOD;return lalal;
}
LL Q[N];
void dfs (LL x)
{Q[++Q[0]]=x;for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==f[x]) continue;f[y]=x;dfs(y);}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%I64d",&n);for (LL u=1;u<n;u++){LL x,y,z;scanf("%I64d%I64d%I64d",&x,&y,&z);x++;y++;init(x,y,z);init(y,x,z);k[x]++;k[y]++;d[x]++;d[y]++;b[x]+=z;b[y]+=z;}dfs(1);for (LL u=Q[0];u>=2;u--){LL x=Q[u];if (d[x]==1) continue;//叶子不管了.. LL tmp=pow(k[x],MOD-2);k[f[x]]=(k[f[x]]-tmp)%MOD;b[f[x]]=(b[f[x]]+b[x]*tmp%MOD)%MOD;}long long ans;ans=(b[1]*pow(k[1],MOD-2)%MOD+MOD)%MOD;printf("%I64d\n",ans);return 0;
}