计数与概率期望小结

好久没写过总结了,感觉有的东西不写一写很容易忘,还是写一点东西。

计数

组合数

BZOJ4870 [SHOI2017] 组合数问题

题意

给定四个整数 $n,p,k,r$ ,求 $\displaystyle\sum_{i = 0}^{\infty} \binom{nk}{ik+r} \bmod p$ 。

$1 \le n \le 10^9,0 \le r < k \le 50,2 \le p \le 2^{30} - 1$ 。

技巧:考虑组合数的意义,转化问题。

题解

考虑上面的组合数的意义,我们可以将题目转化为,我们要在 $nk$ 个物品中,选出 $\bmod p = r$ 个物品的方案数。这个东西可以直接DP,然后矩阵乘法加速即可。

UOJ275 [清华集训2016] 组合数问题

题意

小葱想知道如果给定 $n,m$ 和 $k$,对于所有的 $0 \le i \le n,0 \le j \le \min(i,m)$ 有多少对 $(i,j)$ 满足 $\binom{i}{j}$ 是 $k$ 的倍数。

答案对 $10^9+7$ 取模。

$1 \le n,m \le 10^{18},1 \le t,k \le 100$,且 $k$ 是一个质数。

技巧:利用卢卡斯定理对于条件转化

题解

首先由卢卡斯定理,原题的限制可以转化为,求数对 $(i,j)$ 满足 $(i,j)$ 在 $k$ 进制下,必定存在某一位,满足 $i$ 在这一为比 $j$ 小,且 $i \le n,j \le min(i,m)$ 。这个证明很简单,直接用卢卡斯定理,一直迭代下去就可以了。

接下来用一个数位DP做一下就可以了。记 $dp[i][0/1][0/1][0/1][0/1]$ 表示当前填到了第 $i$ 位,第一个数是否达到上界,第二个数是否达到 $m$ 的上界,第二个数是否达到 $i$ 的上界,是否存在某一位满足第一个数的某一位小于第二个数。注意第二个数的两个上界是要分开记的,否则转移的时候会转移串。这个自己写的时候会发现这个问题。转移枚举两个数下一位分别是什么即可。

UOJ300 [CTSC2017] 吉夫特

题意

给定一个长度为 $n$ 的数列 $a_i$ ,求有多少个长度不小于 $2$ 的子序列 $a_{b_1},a_{b_2},\cdots,a_{b_k}$,满足 $\displaystyle\prod_{i = 2}^{k} \binom{a_{b_{i - 1}}}{a_{b_i}} \bmod 2 > 0$ 。

$1 \le n \le 211985,a_i \le 233333$ ,$a_i$ 互不相同。

技巧:卢卡斯定理转化条件,利用分块思想平摊掉修改与查询的复杂度。

题解

首先,和上一题一样,利用卢卡斯定理转化条件,可以得到,我们只要求有多少长度不小与 $2$ 的子序列 $a_{b_1},a_{b_2},\cdots,a_{b_k}$ ,满足后一个数是前一个数的子集。

不难想到记 $dp[i][S]$ 表示到第 $i$ 个数,当前最靠后的数为 $S$ 的方案。直接的话,由于 $a_i$ 互不相同,复杂度是 $3^{18}$ ,不足以通过此题。

我们考虑我们转移的时候,如果我们记的 $S$ 是上面这种,那么每次修改是 $O(1)$ ,查询的时候复杂度最坏是 $2^{18}$ ;如果我们记的 $dp[i][S]$ 是所有 $S$ 的子集的方案,那么我们每次修改的时候,复杂度最坏是 $2^{18}$ ,但是查询是 $O(1)$ 的。我们考虑平摊一下复杂度,即我们即 $dp[i][S1][S2]$ 表示到第 $i$ 个数,最后一个数前 $9$ 位为 $S1$ ,后 $9$ 位为 $S2$ 或者 $S2$ 的子集的方案数。这样相当于把修改和查询最坏复杂度都降到了 $O(2^9)$ ,总时间复杂度即为 $O(6^9)$ 。

其他

课件里还讲了如何 $O(\sqrt{n}\log n)$ 求组合数,不过分块打标更加优秀,也就没啥意义了。

组合计数

AGC001E BBQ HARD

题意

有 $n$ 组烧烤材料,每组有 $a_i$ 片牛肉和 $b_i$ 片青椒。需要从中选择两组材料,并把材料串在一起排列,问有多少种排列方案。两种方案不同,当且仅当选择的材料不一样,或者排列的方式不一样。

$n \le 200000,a_i,b_i \le 2000$ 。

技巧:组合意义的转化

题解

考虑把题目转化为,二维平面内有 $2n$ 个点。每组材料对应点 $(-a_i,-b_i)$ 和点 $(a_i,b_i)$ 。接下来方案数就是所有第三象限的点走到第一象限的方案数之和,减去自己走到自己的方案数。

AGC002F Leftmost Ball

题意

有 $n$ 种颜色的球,编号为 $1$ 至 $n$ ,每种有 $k$ 个。将这 $nk$ 个球排成一排,将每种颜色从左至右第一个球染成颜色 $0$ 。求最后能得到多少种不同的序列。

$1 \le n,k \le 2000$ 。

技巧:计数限制条件的转化

题解

由题目的限制,可以发现一个这样的性质,从左到右第 $i$ 个 $0$ 的左边最多出现了 $i - 1$ 种颜色。然后每次填的时候会有两种决策,一种是加入一个新的颜色,另一种是加一个 $0$ 。由于每种颜色个数还有限制,直接顺次填还是不方便,因此可以一次填上所有一种颜色,这个可以直接用组合数计算。然后就可以记 $dp_{i,j}$ 表示确定了 $i$ 个 $0$ 和 $j$ 种颜色的方案数,转移比较显然了。

简单计数

题意

$n$ 个$[1,m]$ 内的变量,其中 $i$ 不能连续出现超过 $a_i$ 次,求方案数。

$1 \le a_i \le n \le 5000,1 \le m \le 10^5$ 。

技巧:简化相同转移降低复杂度

题解

首先不难想到一个 $dp$ 。设 $dp[i][j]$ 表示前 $i$ 个数,最后一个数为 $j$ 的方案数。容易写出一个简单的 $dp$ 。
$$
dp[i][j] = \sum_{k=1}^{m}dp[i-1][ k] - \sum_{k=1}^{m}[k \not= j] dp[i-a_i-1][k]
$$
直接转移是 $O(nm)$ 的,需要优化。注意到对于 $a_i$ 相同的数,$dp$ 值是相同的,因此可以一起转移。复杂度优化为 $O(n^2 + m)$ 。

FFT辅助计数

简单树题

题意

给定一个 $n$ 个点的树,对于每一个 $1 \le k \le n$ ,求有多少个 $k$ 个点的集合可以用至多一条路径覆盖。

$1 \le n \le 10^5$

技巧:点分治+FFT的树上计数的套路

题解

如果我们将一个合法的点集记在满足条件的长度最小的链上,那么我们的计数会更加方便。考虑树上一条长度为 $i$ 的路径,由于我们把贡献记在了长度最小的路径上,因此我们必须强制选择路径两端的点,那么我们记在这条路径上的方案数就是 $2^{i-1}$ 。因此我们只要统计对于所有的 $i$ ,长度为 $i$ 的路径条数。这个问题可以用经典的点分治+FFT实现。

生成函数

生成函数最基本的用法,辅助计数

BZOJ3771 Triple

题意

有若干个互不相同的正整数 $a_i$ ,从中选出至多三个,求选出的数的和为每种情况的方案数。

$a_i \le 40000$。

技巧:生成函数的基本运用

题解

算是生成函数中比较简单的题目了。我们可以直接构造普通型生成函数,然后容斥掉重复取同一个的贡献就可以了。

此外,生成函数还可以用来优化一些递推式的计算。

举个很简单的例子,我们构造一个斐波那契数列的生成函数为 $F(x) = \displaystyle\sum_{i = 0}^{\infty}fib_nx^n$ ,由于 $fib_i = fib_{i - 1} + fib_{i - 2},f_0 = f_1 = 1$ ,所以 $F(x) = F(x)x + F(x)x^2 + 1$ 。于是 $F(x) = \frac{1}{1 - x - x^2}$ 。于是可以用多项式求逆,解出 $F(x)$ 。

注意,写生成函数的时候一定不要忘了边界项!

虽然这个问题直接递推更快,但对于某些问题,就必须利用到生成函数了,比如下面这道题,也是这类问题的一个模板题。

CF438E The Child and Binary Tree

题意

给出一个正整数集合 $c_i$ ,对于所有 $1 \le i \le m$ 求出有多少形态不同的二叉树点权均属于这个集合且点权和为 $i$ 。

$1 \le m,c_i \le 10^5$ 。

技巧:生成函数解决递推式的问题。

题解

我们设 $f(i)$ 表示二叉树点权和为 $i$ 的方案数,$a(x)$ 表示是否存在 $c_i = x$ 。所以我们会有 $f(0) = 1,f(i) = \displaystyle\sum_{x,y}f(x)f(y)a(i-x-y)$ 。

如果我们用 $F(x)$ 表示 $f(i)$ 的生成函数,$A(x)$ 表示 $a(i)$ 的生成函数,那么我们会有:
$$
\begin{aligned}
F(x) &= F(x)^2A(x) + 1 \\
\Leftrightarrow F(x) &= \frac{1 \pm \sqrt{1 - 4A(x)}}{2A(x)}
\end{aligned}
$$
然后这个求逆的地方,由于 $A(x)$ 没有常数项,直接求逆会凉掉,因此得转化一下。
$$
F(x) = \frac{2}{1 \pm \sqrt{1 - 4A(x)}}
$$
然后求逆的时候用那个常数项非 $0$ 的解去求即可。

这里多啰嗦一句多项式开方,其实也很简单,同样是利用倍增+FFT去求。假设我们已经求出了在模 $x^n$ 的意义下,$A(x)$ 的平方根 $B’(x)$ ,我们要求 $A(x)$ 在模 $x^{2n}$ 的意义下,$A(x)$ 的根式 $B(x)$ 。于是我们会有
$$
B^2(x)-2B(x)B’(x)+B’^2(x)\equiv 0\pmod {x^{2n}}
$$
解得
$$
B(x)=\frac{A(x)+B’^2(x)}{2B’(x)}
$$
于是求逆一下就可以了。

第一类斯特林数

第一类斯特林数 $S_1(n,m)$ 表示把 $n$ 个元素排成 $k$ 个环的方案数,于是我们可以直接得到:
$$
S_1(n,k) = S_1(n - 1,k - 1) + (n - 1)S_1(n -1,k)
$$
第一类斯特林数的生成函数可以用这个东西表示:
$$
\sum_{i = 0} ^ {n}S_1(n,i) x^i = \prod_{i = 0}^{n - 1}(x + i)
$$
这个生成函数可以直接利用之前的递推式直接得到。由于 $S_1(n,i)$ 对应的生成函数的项的次数为 $i$ ,我们可以对着递推式理解一下。当我们给这个生成函数乘上一个新的项 $(x + i)$ 的时候,如果我们在这里选择乘上 $x$ ,相当于给我们的多项式次数 $+1$ ,对应递推式中 $S_1(n - 1,k - 1) \rightarrow S_1(n,k)$ ,如果我们在这里选择乘上 $i$ ,相当于多项式的次数不变,但是乘上了一个 $i$ 的系数,对应递推式中 $(n - 1)S_1(n - 1,k) \rightarrow S_1(n,k)$ 。

这样的话,第一类斯特林数就可以用分治+FFT在 $O(n \log ^ 2 n)$ 的时间内求出来了。但是这还不够优秀。利用倍增+FFT,我们可以把复杂度优化到 $O(n \log n)$。

具体来说,令 $\displaystyle F_n(x) = \prod_{i = 0}^{n - 1}(x + i)$,那么 $F_{2n}(x) = F_n(x) F_n(x + n)$ 。而
$$
\begin{aligned}
F_n(x+n) &= \sum_{i = 0}^{n - 1}S_1(n,i)(x+n)^i
\\&= \sum_{i = 0}^{n - 1}S_1(n,i)\sum_{j=0}^i \binom{i}{j}x^jn^{i-j}
\\&= \sum_{j = 0}^{n - 1}x^j \sum_{i=j}^{n - 1} \binom{i}{j}S_1(n,i)n^{i-j}
\end{aligned}
$$
把式子拆开,就可以发现这是一个卷积形式。于是我们可以用倍增+FFT在 $O(n\log n)$ 的时间内求解。

此外还有一个定义叫有符号第一类斯特林数,它的值就是在 $S(n,k)$ 的基础上乘上一个 $(-1)^{n-k}$ 。它的生成函数为
$$
\sum_{i = 0} ^ {n}S_1(n,i) x^i = \prod_{i = 0}^{n - 1}(x - i)
$$

第一类斯特林数和上升下降幂还有这样的转化:
$$
\begin{aligned}
x^{\underline{n}} &= \sum_{i = 0}^{n}S_1(n,i)x^i \\
x^{\overline{n}} &= \sum_{i = 0}^{n}S_1(n,i)(-1)^{n - i}x^i
\end{aligned}
$$
其中 $x^{\underline{i}}$ 与 $x^{\overline{i}}$ 分别表示 $x$ 的 $i$ 次下降幂与上升幂。

第二类斯特林数

第一类斯特林数 $S_2(n,m)$ 表示把 $n$ 个元素分成 $k$ 个非空集合的方案数,于是我们可以直接得到:
$$
S_2(n,k) = S_2(n - 1,k - 1) + kS_2(n -1,k)
$$
利用容斥原理,我们可以得到第二类斯特林数的另外一个求法:
$$
S_2(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^kC(m,k)(m-k)^n
$$
这里的容斥利用的是,枚举有几个集合是空的。注意到每个集合都是一样的,所以最后答案要除一个 $m!$。利用NTT可以直接在 $O(n\log n)$ 的时间内求出答案。

第二类斯特林数和上升下降幂还有这样的转化:
$$
\begin{aligned}
x^n &= \sum_{i = 0}^{n}S_2(n,i)x^{\underline{i}}
\ &= \sum_{i = 0}^{n}S_2(n,i)(-1)^{n - i}x^{\overline{i}}
\end{aligned}
$$
其中 $x^{\underline{i}}$ 与 $x^{\overline{i}}$ 分别表示 $x$ 的 $i$ 次下降幂与上升幂。

CF932E Team Work

题意

求 $\displaystyle\sum_{i=0}^{n}C(n,i) \times i^k$ 的值。

$1 \leq n \leq 10^9,1 \leq k \leq 5 \times 10^3$ 。

技巧:斯特林数的经典转化

题解

利用普通幂与下降幂在第二类斯特林数的转化,我们可以得到:
$$
\begin{aligned}
\sum_{i=0}^{n}C(n,i) \times i^k
&= \sum_{i=0}^{n}\binom{n}{i}\sum_{j=0}^{k}S_2(k,j)\binom{i}{j}j! \\
&= \sum_{i=0}^{n}\sum_{j=0}^{k}S_2(k,j) \binom{i}{j} \binom{n}{i}j! \\
&= n!\sum_{i=0}^{n}\sum_{j=0}^{k}S(k,j) \frac{1}{(n-i)!} \frac{1}{(i-j)!} \\
&= n!\sum_{i=0}^{n}\sum_{j=0}^{k}S_2(k,j) \binom{n-j}{n-i} \frac{1}{(n-j)!} \\
&= n!\sum_{j=0}^{k}S_2(k,j)\sum_{i=0}^{n}\binom{n-j}{n-i} \frac{1}{(n-j)!} \\
&= n!\sum_{j=0}^{k}S_2(k,j) 2^{n-j} \frac{1}{(n-j)!} \\
&= \sum_{j=0}^{k}S_2(k,j) 2^{n-j} n^{\underline{j}}
\end{aligned}
$$
于是就做完了,问题的关键一步在于幂次与下降幂的转化。

容斥原理

ARC093F Dark Horse

题意

有 $2^n$ 名选手,编号为 $1$ 至 $2^n$ 。现在这 $2^n$ 名选手将进行 $n$ 轮淘汰赛,决出胜者。若 $x < y$ ,则 $x$ 能够战胜 $y$ 。但有 $m$ 个例外,$1$ 号选手会输给这 $m$ 个选手。问有多少中排列方式使得 $1$ 号选手取得胜利。

$n,m \le 16$ 。

技巧:容斥之后,利用DP来加速求解

题解

为了方便,定义这 $m$ 个人组成的集合为集合 $A$ 。容易发现,与 $1$ 号选手交战的选手,对应了 $n$ 个区间内的编号最小值。如果只算某一个区间中集合 $A$ 有人晋级的方案数,可能会有算重的情况。所以可以想到一个容斥,即计算满足集合 $S$ 所包含的所有区间中,集合 $A$ 有人晋级的方案数。最后容斥一下。

这个东西还是不大好算,于是考虑使用DP计数。设 $dp_{i,j}$ 表示选出了集合 $A$ 中前 $i$ 大的选手,且集合 $S$ 中所包含的区间均有集合 $A$ 中的人晋级的方案数。转移还是比较显然的。

CF995F Cowmpany Cowmpensation

题意

给出一棵 $n$ 个点的有根树,每个点可以有一个 $[1,d]$ 内的整数边权,问有多少种点权满足儿子权值不大于父亲。

$1 \le n \le 3000,1 \le D \le 10^9$ 。

技巧:利用容斥降低DP的复杂度

题解

容易想到枚举这棵树内一共出现了多少种数字,然后用组合数去计算最后的答案。但是直接DP的话,合并的时候你需要枚举重复的数字,复杂度相当高,需要简化一下问题。

考虑容斥,将恰好 $j$ 种数字转化为至多 $j$ 种数字。设 $dp_{i,j}$ 表示以 $i$ 为子树,至多出现了 $j$ 种数字的方案数。转移的时候记一个前缀和就可以做到 $O(n^2)$ 的复杂度。

概率与期望

题目我做了一些删减,过水太难的就删掉了……

普通期望题

概率与期望题,首先记住:概率顺推,期望倒推。因为期望顺推的话,你还需要多求一个概率。在不好求概率的时候倒推期望是最合适的。

CF605E Intergalaxy Trips

题意

有 $n$ 个点,每天 $i$ 号点到 $j$ 号点的有向道路有 $p_{i,j}$ 的概率开放。每天可以走一条开放的道路或者留在原地,求从 $1$ 号点走到 $n$ 号点最优的期望时间。注意,你的策略可以随着道路的开放与否做出改变。

$1 \le n \le 1000$。

技巧:期望倒推的利用,与贪心的结合

题解

我们设 $f(x)$ 表示从 $x$ 节点到 $n$ 节点最优时间的期望,那么我们的最优策略肯定是,在所有你能到的节点中,走向期望时间最短的点。如果这个点的期望时间大于本身,那么就留在这个点,等待下一次。

那么我们可以考虑按照期望的大小从小到大确定每个点的答案。每次从所有未确定的点中,选择一个当前期望值最小的点。由于我们不会走向期望时间比自己大的点,因此,这样做是正确的。我们设 $a_i$ 表示 $f(x)$ 第 $i$ 小的点的编号,那么我们有:
$$
f(a_i) = 1 + \sum_{j = 1}^{i}f(a_i) P_{a_i,a_j}\prod_{k = 1}^{j - 1}(1 - p_{a_i,a_k})
$$
这里在确定一个点之后,对于每个未确定的点维护一下新的答案,就可以在 $O(n^2)$ 的时间内解决了。

BZOJ5058 期望逆序对

题意

给定一个 $1$ 到 $n$ 的排列,求 $k$ 次随机交换之后,期望逆序对的数量。

$n \le 500000,k \le 10^9$ 。

技巧:考虑某一对或某个物品对于答案的贡献;考虑末状态的期望

题解

考虑每对数字对答案的贡献。每对数字 $a_i,a_j$ 在末状态的时候,所处位置有三种可能的情况,位于 $i$ ,位于 $j$ ,位于其他的位置。注意到在这里,每个点位于其他位置的概率是均等的。因此 $(i,j)$ 这个数对的位置情况可以归为 $7$ 种。把这 $7$ 种情况的转移写成一个矩阵,就可以求出每种位置情况的概率。

直接对于每一个数对统计答案的话,时间复杂度仍然是 $O(n^2)$ 的,于是我们要用一个BIT来统计贡献。具体实现还是看代码比较好……

CF838D Airplane Arrangements

题意

有 $n$ 个人排成一排,有 $m$ 个人依次进场选位置。每个人开始会选择一个方向(从左至右或从右至左)并选择一个位置。他会走到他选择的那个位置,如果那个位置被人占用了,他会沿着他选择的方向一路走到第一个空位并坐下。求有多少种情况满足每个人都有座位。

$1 \le m \le n \le 10^6$ 。

技巧:巧妙的建模,找到概率相同的量

题解

把所有位置看成一个 $n + 1$ 个点的环。其中第 $n + 1$ 个点是一个特殊点,如果有人占据了这个点,那么意味着有人没有座位。如果我们假设这 $m$ 个人可能以 $n + 1$ 号点为起点,这显然不会影响合法的答案。但是这样修改了一下之后,每个人坐在每个位置上的概率是均等的。所以答案就是 $\frac{n + 1 - m}{n + 1}(2n+2)^m$。

树上高斯消元解决树上期望问题

这种题主要还是要熟悉一下套路,一般来讲,可以把 $dp$ 的式子写成 $f(x) = A_xf(fa[x]) + B_x$。然后从下到上一路推到根,就可以求出整棵树的 $dp$ 值。

LOJ2542 随机游走

题意

给定一棵 $n$ 个结点的树,你从点 $x$ 出发,每次等概率随机选择一条与所在点相邻的边走过去。

有 $Q$ 次询问,每次询问给定一个集合 $S$,求如果从 $x$ 出发一直随机游走,直到点集 $S$ 中所有点都至少经过一次的话,期望游走几步。

特别地,点 $x$ 视为一开始就被经过了一次。

$1 \le n \le 18,1 \le Q \le 5000$ 。

技巧:树上高斯消元;MinMax容斥

题解

题意等价于,给定一个点集,求经过这个点集里的点的时间的Max的期望。Max的期望可以说相当不好求,这里考虑利用MinMax容斥,将时间Max的期望转化为时间Min的期望。MinMax容斥的式子大概长这样:
$$
\displaystyle \max\{S\}=\sum_{T\subseteq S}(-1)^{|T|-1}\min\{T\}
$$
证明大概可以这样考虑。设 $\max\{S\} = x$,将除了 $\{x\}$ 与 $\varnothing$ 之外,将所有集合两两配对。配对方式就是将一个不含 $x$ 的集合和这个集合加上 $x$ 这个元素形成的集合配对。这样两个集合的最小值肯定是相等的,会相互抵消。最后剩下的集合中,空集没有最小值,故答案即为 $x$ 。

MinMax容斥之后,我们就只要求第一次经过某个点集的期望时间了。设 $f(x,S)$ 表示从 $x$ 出发,第一次经过集合 $S$ 中的点的期望时间。这个东西可以分两类讨论:

若 $x \in S$ ,则 $f(x) = 0$;

若 $x \not\in S$ ,则$\displaystyle f(x)=[f(fa[x])+1+\sum (f(ch[x])+1)] \times \frac{1}{deg[x]}$。

利用树上高斯消元,将 $f(x)$ 表示为 $A(x)f(fa[x]) + B(x)$ 的形式。于是我们有
$$
\displaystyle (1-\frac{\sum A_v}{deg[u]}) f(u) = \frac{1}{deg[u]}f(\mathrm{fa}[u])+(1+\frac{\sum B_v}{deg[u]})
$$
把左边除过去,然后就可以得到答案了。

Trip

题意

给定一棵 $n$ 个点,以 $1$ 号点为根的树,每个点为黑色或白色。从 $1$ 号点出发,每次随机走向一个相邻的节点。如果该点为黑色或第一次经过该点,则计数器加 $1$ 。如果走到叶子节点整个过程将结束。求计数器的值的期望。

$n \le 10^6$ 。

技巧:树上高斯消元,期望综合难题;大胆设出未知数。

题解

首先考虑只有黑点的时候,该怎么做。黑点是经过一次就算一次贡献,如果我们设 $f(x)$ 表示从 $x$ 出发,经过的黑点的期望个数,那么我们就可以得到一个DP方程
$$
f_i = [i is black] + [deg[i] > 1]\frac{\sum f(j)}{deg[i]}
$$
其中 $j$ 为所有与 $i$ 相邻的点。那么这里直接用树上高斯消元即可解决。

接下来考虑只有白点的情况。由于白点只在第一次经过的时候做出贡献,那么我们只需求出经过白点的概率 $g_i$ 。由于当我们从 $1$ 号点出发的时候,想要经过 $i$ ,必须经过 $fa_i$ 。我们设 $h_i$ 为从 $fa_i$ 走到 $i$ 节点的概率,那么我们有 $g_i = g_{fa_i} \times h_i$ 。

考虑我们该如何求 $h$ 。设 $a_i$ 表示从 $i$ 走到 $fa_i$ 的概率,那么我们有这样一个式子:
$$
h_i = \frac{1}{deg_{fa_i}}(1 + h_ih_{fa_i} + \sum a_jh_i)
$$
其中 $j$ 是 $i$ 的儿子节点。

解释一下这个式子。第一项表示我第一步就到了 $i$ 节点;第二项表示我第一步走到了父亲节点,那么我为了走到 $i$ 节点,就要往下走两步,概率分别为 $h_{fa_i}$ 与 $h_i$ 。第三项表示我第一步走到了其他的儿子节点,那么我需要先往上走一步,再往下走一步。

为了求 $h$ 我们还得求 $a$ 。不过所幸 $a$ 求起来是很简单的。容易发现这样一个式子:
$$
a_i = \frac{1}{deg_i}(1+\sum a_ja_i)
$$
同样 $j$ 为 $i$ 的儿子节点。这个式子理解起来很简单。第一项就是一步走对,第二项就是往下走了,然后要往上走两步。

以上的 $h$ 和 $a$ 均用树上高斯消元都可以求出来,于是问题终于解决啦!