【CF802L】Send the Fool Further! (hard)
题意：给你一棵n个节点的树，每条边有长度，从1号点开始，每次随机选择一个相邻的点走，走到一个叶子时就停止，问期望走的总路程。
$n\le 10^5$
题解：很自然想到游走那题，于是想到高斯消元，但是正常高斯消元是$O(n^3)$的。不过我们有一个套路：在树上进行高斯消元的复杂度是$O(n)$的。
先列出方程：设f(x)表示从x开始期望还要走的路程，x的度数是d，那么$f(x)=\frac {f(fa)+len} d+\frac {\sum f(ch)+len} d$。而在叶子处，方程是形如$f(x)=k\cdot f(fa)+b$的，将其代入父亲的方程，便可以使父亲的方程也变成$f(x)=k\cdot f(fa)+b$的形式，这样一路消上去，就得到了根节点的答案了。
如果想知道所有点的答案的话，再一路消下来就好了。想不到这个套路在pkuwc上用到了233。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll P=1000000007;
int n,cnt;
int fa[maxn],to[maxn<<1],nxt[maxn<<1],head[maxn],q[maxn],d[maxn];
ll k[maxn],b[maxn],f[maxn];
inline ll pm(ll x,ll y)
{
ll z=1;
while(y)
{
if(y&1) z=z*x%P;
x=x*x%P,y>>=1;
}
return z;
}
inline void add(int a,int b)
{
to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x)
{
q[++q[0]]=x;
for(int i=head[x];i!=-1;i=nxt[i]) if(to[i]!=fa[x]) fa[to[i]]=x,dfs(to[i]);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i,x,y,z;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) x=rd()+1,y=rd()+1,z=rd(),add(x,y),add(y,x),k[x]++,k[y]++,d[x]++,d[y]++,b[x]+=z,b[y]+=z;
dfs(1);
for(i=n;i>=2;i--) if(d[q[i]]!=1)
{
x=q[i];
ll tmp=pm(k[x],P-2);
k[fa[x]]=(k[fa[x]]-tmp)%P;
b[fa[x]]=(b[fa[x]]+b[x]*tmp)%P;
}
f[1]=b[1]*pm(k[1],P-2)%P;
printf("%lld",(f[1]+P)%P);
return 0;
}