树上随机游走

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

需要用到的定义

• \(T=(V,E)\): 所讨论的树
• \(d(u)\):\(u\) 结点的度数
• \(w(u,v)\):\(u\) 结点与 \(v\) 结点之间的边的边权
• \(p_u\):\(u\) 结点的父结点
• \(\textit{son}_u\):\(u\) 结点的子结点集合
• \(\textit{sibling}_u\):\(u\) 结点的兄弟结点集合

向父结点走的期望距离

设 \(f(u)\) 代表 \(u\) 结点走到其父结点 \(p_u\) 的期望距离，则有：

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

化简如下：

初始状态为 \(f(\text{leaf}) = 1\)。

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

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

向子结点走的期望距离

设 \(g(u)\) 代表 \(p_u\) 结点走到其子结点 \(u\) 的期望距离，则有：

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

化简如下：

初始状态为 \(g(\text{root}) = 0\)。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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 != 1) g[u] = g[p] + f[p] - f[u];
  for (auto v : G[u]) {
    if (v == p) continue;
    dfs2(v, u);
  }
}

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用