一道日常题的题解

今天校内某比赛的一道题。

感觉挺有意思的于是来写一篇题解。

题面甚至是纯英文，怕不是防 AK 用的。

其实我是可以 AK 的，不过剩下三道题（其中还有一道大模拟懒得写了）。

顺便一提，其实我睡过去了一整个上午，打开比赛页面的时候已经是比赛开始五个小时了（

给定一棵 $n$ 个点的树，边有边权。从 $1$ 号节点开始，每次等概率随机选择一个相邻节点走过去，到了叶节点就停下来。这里叶节点定义为度数为 $1$ 的节点。保证根节点不满足这个定义。

走过一条边需要消耗的时间等于这条边的边权。求期望多长时间后能停下来。答案对 $10^9+7$ 取模。

$1\leqslant n\leqslant 10^5$。边权范围不重要（反正不爆 int）。

设 $E(u)$ 表示从 $u$ 号节点出发的期望停止时间。根据期望的线性性，我们可以得到

$$E(u)=\frac{1}{\operatorname{deg}u}\sum_{(u,v)}(E(v)+w(u,v))$$

如果 $u$ 号节点已经是叶节点，那么 $E(u)=0$。

当然，这在形式上完全可以视作一个 $n-r$ 个变量和 $n-r$ 个方程构成的线性方程组，其中 $r$ 表示叶节点的数量。

但是考虑到本题的数据范围，这样做的时间复杂度太大了。我们需要换一个思路。

首先我们梳理一下思路（非形式化地）：

考虑到，如果节点 $u$ 的所有子节点都是叶节点，那么 $E(u)$ 只会取决于 $E(f(u))$；而且一定是 $E(f(u))$ 的一次函数。

如果节点 $u$ 存在一个不是叶节点的节点 $v$，但是 $v$ 的所有子节点都是叶节点，那么 $E(v)$ 也是 $E(u)$ 的一次函数，我们就可以在 $E(u)$ 的式子中出现的 $E(v)$ 替换成 $E(u)$。这样整个式子中的待求量还是只会剩下 $E(u)$ 和 $E(f(u))$，也就是说 $E(u)$ 可以表示成 $E(f(u))$ 的一次函数。

如此递推到 $1$ 号节点，那么实际上我们需要求解的只有一个关于 $E(1)$ 的一次方程。

形式化地：

如果一个节点 $u$ 满足

$$E(u)=\alpha(u)E(f(u))+\beta(u)$$

其中 $f(u)$ 表示 $u$ 的父节点，且 $\alpha(u),\beta(u)$ 只与 $u$ 有关而与其他节点无关，那么我们称 $u$ 是可表示的。

显然叶节点都是可表示的。

如果一个节点 $u$ 的所有子节点均是可表示的，那么

$$\begin{aligned} &E(u)\\ =&\frac{1}{\operatorname{deg}u}\sum_{(u,v)}(E(v)+w(u,v))\\ =&\frac{E(f(u))+w(u,f(u))}{\operatorname{deg}u}+\frac{1}{\operatorname{deg}u}\sum_{(u,v)\wedge v\neq f(u)}(E(v)+w(u,v))\\ =&\frac{E(f(u))+w(u,f(u))}{\operatorname{deg}u}+\frac{1}{\operatorname{deg}u}\sum_{(u,v)\wedge v\neq f(u)}(\alpha(v)E(u)+\beta(v)+w(u,v)) \end{aligned}$$

整理可得

$$\left(1-\frac{1}{\operatorname{deg}u}\sum_{(u,v)\wedge v\neq f(u)}\alpha(v)\right)E(u)=\frac{E(f(u))+w(u,f(u))}{\operatorname{deg}u}+\frac{1}{\operatorname{deg}u}\sum_{(u,v)\wedge v\neq f(u)}(\beta(v)+w(u,v))$$

即 $u$ 是可表示的。

于是我们可以容易地注意到，所有节点均是可表示的，且 $\alpha,\beta$ 均是可求解的。

考虑 $1$ 号节点，有

$$E(1)=\alpha(1)E(f(1))+\beta(1)$$

这里 $f(1)=0$，即 $E(f(1))=0$，我们就可以得到

$$E(1)=\beta(1)$$

而 $E(1)$ 正是本题要求的答案。