跳转至

树上随机游走

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

需要用到的定义

  • \(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\) 的期望距离,则有:

\[ f(u) = \cfrac{w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v) + f(u))}{d(u)} \]

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

化简如下:

\[ \begin{aligned} f(u) &= \cfrac{w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v) + f(u))}{d(u)} \\ &= \cfrac{w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v)) + (d(u)-1)f(u)}{d(u)} \\ &= w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v)) \\ &= \sum\limits_{(u,t) \in E}w(u,t) + \sum\limits_{v \in \textit{son}_u}f(v) \end{aligned} \]

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

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

\[ f(u) = d(u) + \sum\limits_{v \in \textit{son}_u}f(v) \]

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

向子结点走的期望距离

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

\[ g(u) = \cfrac{w(p_u,u) + \left(w(p_u,p_{p_u})+g(p_u)+g(u)\right) + \sum\limits_{s \in \textit{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) &= \cfrac{w(p_u,u) + \left(w(p_u,p_{p_u})+g(p_u)+g(u)\right) + \sum\limits_{s \in \textit{sibling}_u}(w(p_u,s)+f(s)+g(u))}{d(p_u)} \\ &= \cfrac{w(p_u,u) + w(p_u,p_{p_u}) + g(p_u) + \sum\limits_{s \in \textit{sibling}_u}\left(w(p_u,s)+f(s)\right)+(d(p_u)-1)g(u)}{d(p_u)} \\ &= w(p_u,u) + w(p_u,p_{p_u}) + g(p_u) + \sum\limits_{s \in \textit{sibling}_u}(w(p_u,s)+f(s)) \\ &= \sum\limits_{(p_u,t) \in E}w(p_u,t) + g(p_u) + \sum\limits_{s \in \textit{sibling}_u}f(s) \\ &= \sum\limits_{(p_u,t) \in E}w(p_u,t) + g(p_u) + \left(f(p_u)-\sum\limits_{(p_u,t) \in E}w(p_u,t)-f(u)\right) \\ &= g(p_u) + f(p_u) - f(u) \end{aligned} \]

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

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

C++
 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);
  }
}