跳转至

树上随机游走

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

需要用到的定义

  • : 所讨论的树
  • : 结点 的度数
  • : 结点 与结点 之间的边的边权
  • : 结点 的父结点
  • : 树的根结点
  • : 结点 的子结点集合
  • : 结点 的兄弟结点集合

向父结点走的期望距离

代表 结点走到其父结点 的期望距离,则有:

分子中的前半部分代表直接走向了父结点,后半部分代表先走向了子结点再由子结点走回来然后再向父结点走;分母 代表从 结点走向其任何邻接点的概率相同。

化简如下:

对于叶子结点 ,初始状态为

当树上所有边的边权都为 时,上式可化为:

子树的所有结点的度数和,也即 子树大小的两倍 (每个结点连向其父亲的边都有且只有一条,除 之间的边只有 点度数的贡献外,每条边会产生 点度数的贡献)。

向子结点走的期望距离

代表 结点走到其子结点 的期望距离,则有:

分子中的第一部分代表直接走向了子结点 ,第二部分代表先走向了父结点再由父结点走回来然后再向 结点走,第三部分代表先走向 结点的兄弟结点再由其走回来然后再向 结点走;分母 代表从 结点走向其任何邻接点的概率相同。

化简如下:

初始状态为

代码实现(以无权树为例)

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