树上高消

高斯消元我们都知道，是难以优化的三方算法，我们在这里限定高斯消元解决的是线性方程组问题。

引入——树上随机游走

顾名思义，给定每个点到每个邻居的系数，有一些点是终止态，到达后不能再游走，求每个节点期望经过次数（这个次数对于终止态来说就是到达该态的概率）。

设期望经过次数是 $f_x$ ，其满足关系式 $f_x=(x\text{ 上的初始点数})+\sum_{v\leftrightarrow x} f_vp(v\to x)[v\text{ 不是终止态}]$ ，我们立刻得到了 $n$ 个方程，使用高斯消元进行 $n^3$ 的解方程即可。

但这是树上，我们不满足于这么慢的复杂度，考虑定一个根，每个点的式子里只有父亲、自己、儿子，而叶子只有自己和父亲，所以我们可以自下而上，先把叶子和叶子父亲联立，在叶子父亲的方程中消掉叶子这个元，然后逐级向上，一共需要进行 $\mathcal O(n)$ 次操作，将根处的值推出后我们可以向下递推解决。

既然有了线性复杂度，我们当然不能再用矩阵来存储方程的系数了，考虑形式化上述过程，由于最终每个点的方程中只有自己和父亲，我们设 $f_x=A_xf_{fa_x}+B_x$ ，将转移式中儿子 $v$ 的 $f_v$ 替换成 $A_vf_{x}+B_v$ ，转移式中就只剩下 $x,fa_x$ ，我们就可以得到 $A_x,B_x$ 关于 $A_v,B_v$ 的转移式。

求出 $A_x,B_x$ 后从上往下递推即可。

具体式子看上去总是十分繁琐，直接打出来十分吓人，然而我们的流程并不困难。

扩展：涉及祖父

来观察如下式子（ $Fa_x$ 表示祖父，其意义为原树边和祖父边均保留后，等概率走一条出边，到某个点的期望步数）：

$f_{x}=1+\frac{1}{d_x}(f_{fa_x}+f_{Fa_x}+\sum_{fa_v=x}f_v+\sum_{Fa_y=x}f_y)$

用相同的想法，我们设 $f_x=A_xf_{Fa_x}+B_xf_{fa_x}+C_x$ 即可，然后我们把 $f_v$ 和 $f_y$ 均代换（ $f_y$ 代换后出现的 $f_v$ 也代换），我们就能得到 $A_x,B_x,C_x$ 从 $v,y$ 转移而来的式子。

求出 $A_x,B_x,C_x$ 后从上往下递推即可。

扩展：子树

每个点以 $p_x$ 概率跳到父亲，以 $(1-p_x)\frac{1}{siz_x}$ 概率跳到子树中的每个点，求到某个点的期望步数。

$f_x=1+p_xf_{fa}+\frac{1-p_x}{siz_x}\sum_{v\in sub_x}f_v$

暴力消元的话，每个点要把每个祖先中自己的部分都消掉，复杂度平方。

但我们发现仍然可以消成 $f_x=A_x f_{fa}+B_x$ 的形式，那么我们直接设这个，然后开始代换。

我们发现，节点 $v$ 在代换的过程中，对其祖先 $y$ 的贡献是 $B_y\prod_{t\in[v,y)}A_t$ ，我们不妨设 $C_y=\sum_v\prod_{t\in[v,y)}A_t$ ，则转移式也可以写成：

$f_x=1+p_xf_{fa}+\frac{1-p_x}{siz_x}(C_xf_x+\sum_{v\in sub_x,v\ne x}B_vC_v)$

显然 $C_x=\sum_vA_vC_v$ 可以递推，所以这个问题也可以线性求解。

扩展：祖先

更改“子树”部分的题意，求每个点的期望经过次数，则每个点需要统计到它的点们，转移式变为：

$f_x=\sum_{v\in son_x}p_xf_{v}+\sum_{y\in anc_x}\frac{1-p_y}{siz_y}f_y$

对于祖先其实我们不是很会处理，所以我们设 $g_x=\sum_{y\in anc_x}\frac{1-p_y}{siz_y}f_y$ ，我们立刻得到 $g_x-g_{fa}=\frac{1-p_x}{siz_x}f_x$ 。

熟悉的形式，我们将转移式最后的一坨改为 $g_x$ ，并把 $f_x,f_v$ 全部换成 $g_x,g_{fa},g_v$ ，则我们又回到了第一部分的问题， $g$ 的关系式是经典的树上高消，消出 $g$ 后我们可以接着求出 $f$ 。