树上直径期望

微积分，多项式，概率期望。

GYM102155B Short Random Problem

题意

给你一颗 $n\;(n\le 80)$ 个点的树，树上的每一条边的长度都是 $[1,n]$ 的随机实数。 求直径的期望长度，对 $10^9+7$ 取模。

题解

总的思路：枚举一条边 $(u,v)$ 计算直径中心在其上的贡献，即 直径中心在该边上的概率 乘 直径长度期望。

设 $f_u(x)=Pr[d(u)\le x]$，即表示 $u$ 到子树中最长链长度小于 $x$ 的概率，这是可以用多项式表示的，而且是一个连续的分段函数，以整数为分段界限。

• 考虑加上一条边：$\displaystyle f(x)=\int_{x-1}^x g(y)\,\mathrm{d}y$ 。

• 考虑多条链中取最大：$f(x)=\prod f_i(x)$。

  因为 $Pr[\max(a,b)\le x]=Pr[a\le x]\times Pr[b\le x]$

考虑 DP 出 $f_u(x)$，对于叶子节点显然 $f(x)=1$。对于任意节点先取最长链再加一条边，形式化地：

$$g_u(x)=\prod_{v\in son(u)} f_v(x)$$

$$f_u(x)=\int_{x-1}^x g_u(y)\,\mathrm{d}y$$

具体实现：

考虑到 $g_u(x)$ 是分段函数，设 $h_i(x)$ 是 $g_u(x)$ 第 $i$ 个函数的积分函数，包含区间 $(i-1,i]$。对于一个 $x \in R$，设 $y = \left \lfloor x\right \rfloor$，则

$$f_u(x) = h_y(x) - h_y(y)+h_{y-1}(y-1)-h_{y-1}(x-1)$$

对于每个属于不同区间的 $f_u(x)$ 分开来计算，然后特判最后一个新加的区间即可，知道了 $f_u(x)$ 的计算过程， $f(x)$ 是分段函数 也就不证自明了。

---

考虑通过 $f(x)$ 求我们要的期望。事先约定，考虑边 $(u,v)$ 时，以下 $f_u(x)$ 都以 $v$ 为根，同理 $f_v(x)$ 都以 $u$ 为根。

若 $u,v$ 之一为叶子节点，不妨设 $v$ 为叶子节点。设 $(u,v)$ 边权为 $l$，$u$ 到子树最长链长度为 $d(u)$，若要直径中心在 $(u,v)$ 上需要 $d(u)\le l$，即 $f_u(l)$ ，直径长度的期望即 $\mathbb{E}[d(u)+l]$ ，根据期望线性性可以分别求。

$$\mathbb{E}[l]=\int_{0}^{1} lf_u(l)\,\mathrm{d}l \tag{1}$$

相当于枚举 $l$，并对应满足 $d(u)\le l$ 。

$$\mathbb{E}[d(u)]=\int_{0}^{1}\left(\int_{0}^{l} xf'_u(x)\,\mathrm{d}x \right)\,\mathrm{d}l \tag{2}$$

看括号里面，$f'_u(x)$ 即 $Pr[d(u)=x]$ ，表最长链长度为 $x$ 的概率，再 $\times x$ 即期望，则 $\int_{0}^{l} xf'_u(x)\,\mathrm{d}x$ 表示 $d(u)$ 小于等于具体枚举的 $l$ 时 $d(u)$ 的期望。 外边一层积分枚举 $l$。

证明 $f_u'(x)=Pr[d(u)=x]$：

先考虑另一个问题，让你求 $d(u)=x$ 且 $x\in[l,r]$ 的平均概率，显然是 $\dfrac{f_u(r)-f_u(l)}{r-l}$ ，此时考虑 $r$ 无限逼近 $l$，即

$$\lim_{r\to l} \frac{f_u(r)-f_u(l)}{r-l}=\lim_{\Delta x\to 0} \frac{f_u(l+\Delta x)-f_u(l)}{\Delta x}=f'_u(l)$$

证毕。

若是一般情况，不妨令 $d(u)\le d(v)$，显然需要满足 $d(u)\le d(v)\le d(u)+l$，同样 $\mathbb{E}[d(u)+d(v)+l]$ 可以根据期望线性性：

$$\mathbb{E}[l]=\int_{0}^{1} l\left( \int_{0}^{M(u)}f'_u(x)\big(f_v(x+l)-f_v(x)\big)\,\mathrm{d}x \right)\,\mathrm{d}l \tag{3}$$

枚举 $l$ （$M(u)$ 表 $d(u)$ 能取到的最大值），大括号里面对应 $l$ 取该值满足 $l\ge d(v)-d(u)$ 对应的概率，自然枚举 $d(u)$ 的取值 $x$，其概率为 $f_u'(x)$，乘上 $d(v)\in[d(u),d(u)+l]$ 的概率即 $f_v(x+l)-f_v(x)$。

$$\mathbb{E}[d(u)]=\int_{0}^{M(u)}xf_u'(x)\left( \int_{x}^{x+1}f_v'(y)(x-y+1) \,\mathrm{d}y \right) \,\mathrm{d}x \tag{4}$$

枚举 $d(u)$ 的取值 $x$，乘上取该值的概率 $f_u'(x)$，大括号里面表满足 $d(u)\le d(v)\le d(u)+l$ 的概率。枚举 $d(v)$ 的取值 $y\;(y\in[x,x+1])$ 乘上 $d(v)$ 取该值的概率 $f_v'(y)$ ，再乘上 $l\ge y-x$ 的概率 $x-y+1$ 。

$$\mathbb{E}[d(v)]=\int_{0}^{M(v)} yf_{v}'(y)\left(\int_{y-1}^{y} f_{u}'(x)(x-y+1) \,\mathrm{d}x \right)\,\mathrm{d}y \tag{5}$$

同上。

考虑一下以上这坨东西怎么求。$(1),(2)$ 直接积分就完事了。

对于 $(4),(5)$，以 $(4)$ 为例：

$$\begin{aligned} \mathbb{E}[d(u)]&=\int_{0}^{M(u)}xf_u'(x)\left( \int_{x}^{x+1}f_v'(y)(x-y+1) \,\mathrm{d}y \right) \,\mathrm{d}x \\ &=\int_{0}^{M(u)}xf_u'(x)\left( x\int_{x}^{x+1}f_v'(y) \,\mathrm{d}y+\int_{x}^{x+1}f_v'(y)(-y+1) \,\mathrm{d}y \right) \,\mathrm{d}x \\ \end{aligned}$$

对于 $(3)$：

$$\begin{aligned} \mathbb{E}[l]&=\int_{0}^{1} l\left( \int_{0}^{M(u)}f'_u(x)\big(f_v(x+l)-f_v(x)\big)\,\mathrm{d}x \right)\,\mathrm{d}l \\ \mathbb{E}[l]&=\int_{0}^{M(u)}f'_u(x)\int_{0}^{1} l \big(f_v(x+l)-f_v(x)\big)\,\mathrm{d}l\,\mathrm{d}x \\ \mathbb{E}[l]&=\int_{0}^{M(u)}f'_u(x) \left(\int_{0}^{1} lf_v(x+l)\,\mathrm{d}l-f_v(x)\int_{0}^{1} l\,\mathrm{d}l \right)\,\mathrm{d}x \\ \end{aligned}$$

$f_v(x)\int_{0}^{1} l\,\mathrm{d}l=\dfrac{1}{2}f_v(x)$ ，考虑 $\int_{0}^{1} lf_v(x+l)\,\mathrm{d}l$ ，令 $y=x+l$：

$$\begin{aligned} &\int_{0}^{1} lf_v(x+l)\,\mathrm{d}l\\ =&\int_{x}^{x+1} (y-x)f_v(y)\,\mathrm{d}y\\ =&\int_{x}^{x+1} yf_v(y)\,\mathrm{d}y-x\int_{x}^{x+1}f_v(y) \,\mathrm{d}y\\ \end{aligned}$$

那完事了。

题目 $n\le 80$，不用担心卡常，建议封装。

注：积分的基本运算法则（$k$ 为常数，原函数可积）

$$\int_{a}^{b}kf(x)\,\mathrm{d}x=k\int_{a}^{b}f(x)\,\mathrm{d}x$$

$$\int_{a}^{b} \big(f(x)\pm g(x)\big) \,\mathrm{d}x=\int_{a}^{b} f(x)\,\mathrm{d}x\pm \int_{a}^{b}g(x) \,\mathrm{d}x$$

交换求积顺序显然是可以的，跟交换求和顺序差不多。