树上随机游走

给定一棵有根树，树的某个结点上有一个硬币，在某一时刻硬币会等概率地移动到邻接结点上，问硬币移动到邻接结点上的期望距离。

需要用到的定义

$T = (V, E)$ : 所讨论的树
$d (u)$ : 结点 $u$ 的度数
$w (u, v)$ : 结点 $u$ 与结点 $v$ 之间的边的边权
$p_{u}$ : 结点 $u$ 的父结点
$root$ : 树的根结点
${son}_{u}$ : 结点 $u$ 的子结点集合
${sibling}_{u}$ : 结点 $u$ 的兄弟结点集合

向父结点走的期望距离

设 $f (u)$ 代表 $u$ 结点走到其父结点 $p_{u}$ 的期望距离，则有：

f (u) = \frac{w (u, p_{u}) + \sum_{v \in {son}_{u}} (w (u, v) + f (v) + f (u))}{d (u)}

分子中的前半部分代表直接走向了父结点，后半部分代表先走向了子结点再由子结点走回来然后再向父结点走；分母 $d (u)$ 代表从 $u$ 结点走向其任何邻接点的概率相同。

化简如下：

\begin{aligned} f (u) & = \frac{w (u, p_{u}) + \sum_{v \in {son}_{u}} (w (u, v) + f (v) + f (u))}{d (u)} \\ = \frac{w (u, p_{u}) + \sum_{v \in {son}_{u}} (w (u, v) + f (v)) + (d (u) - 1) f (u)}{d (u)} \\ = w (u, p_{u}) + \sum_{v \in {son}_{u}} (w (u, v) + f (v)) \\ = \sum_{(u, t) \in E} w (u, t) + \sum_{v \in {son}_{u}} f (v) \end{aligned}

对于叶子结点 $l$ ，初始状态为 $f (l) = w (p_{l}, l)$ 。

当树上所有边的边权都为 $1$ 时，上式可化为：

f (u) = d (u) + \sum_{v \in {son}_{u}} f (v)

即 $u$ 子树的所有结点的度数和，也即 $u$ 子树大小的两倍 $- 1$ （每个结点连向其父亲的边都有且只有一条，除 $u$ 与 $p_{u}$ 之间的边只有 $1$ 点度数的贡献外，每条边会产生 $2$ 点度数的贡献）。

向子结点走的期望距离

设 $g (u)$ 代表 $p_{u}$ 结点走到其子结点 $u$ 的期望距离，则有：

g (u) = \frac{w (p_{u}, u) + (w (p_{u}, p_{p_{u}}) + g (p_{u}) + g (u)) + \sum_{s \in {sibling}_{u}} (w (p_{u}, s) + f (s) + g (u))}{d (p_{u})}

分子中的第一部分代表直接走向了子结点 $u$ ，第二部分代表先走向了父结点再由父结点走回来然后再向 $u$ 结点走，第三部分代表先走向 $u$ 结点的兄弟结点再由其走回来然后再向 $u$ 结点走；分母 $d (p_{u})$ 代表从 $p_{u}$ 结点走向其任何邻接点的概率相同。

化简如下：

\begin{aligned} g (u) & = \frac{w (p_{u}, u) + (w (p_{u}, p_{p_{u}}) + g (p_{u}) + g (u)) + \sum_{s \in {sibling}_{u}} (w (p_{u}, s) + f (s) + g (u))}{d (p_{u})} \\ = \frac{w (p_{u}, u) + w (p_{u}, p_{p_{u}}) + g (p_{u}) + \sum_{s \in {sibling}_{u}} (w (p_{u}, s) + f (s)) + (d (p_{u}) - 1) g (u)}{d (p_{u})} \\ = w (p_{u}, u) + w (p_{u}, p_{p_{u}}) + g (p_{u}) + \sum_{s \in {sibling}_{u}} (w (p_{u}, s) + f (s)) \\ = \sum_{(p_{u}, t) \in E} w (p_{u}, t) + g (p_{u}) + \sum_{s \in {sibling}_{u}} f (s) \\ = \sum_{(p_{u}, t) \in E} w (p_{u}, t) + g (p_{u}) + (f (p_{u}) - \sum_{(p_{u}, t) \in E} w (p_{u}, t) - f (u)) \\ = g (p_{u}) + f (p_{u}) - f (u) \end{aligned}

初始状态为 $g (root) = 0$ 。

代码实现（以无权树为例）

vector<int> G[MAXN];

void dfs1(int u, int p) {
  f[u] = G[u].size();
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs1(v, u);
    f[u] += f[v];
  }
}

void dfs2(int u, int p) {
  if (u != root) g[u] = g[p] + f[p] - f[u];
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs2(v, u);
  }
}

本页面最近更新：2024/10/9 22:38:42，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, StableAgOH, aofall, CJTracer, CoelacanthusHex, Marcythm, Persdre, shuzhouliu
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用