跳转至

樹上隨機遊走

給定一棵有根樹，樹的某個結點上有一個硬幣，在某一時刻硬幣會等概率地移動到鄰接結點上，問硬幣移動到鄰接結點上的期望距離。

需要用到的定義

  • \(T=(V,E)\): 所討論的樹
  • \(d(u)\): 結點 \(u\) 的度數
  • \(w(u,v)\): 結點 \(u\) 與結點 \(v\) 之間的邊的邊權
  • \(p_u\): 結點 \(u\) 的父結點
  • \(\textit{root}\): 樹的根結點
  • \(\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} \]

對於葉子結點 \(l\)，初始狀態為 \(f(l) = w(p_l, l)\)。

當樹上所有邊的邊權都為 \(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\)。

代碼實現（以無權樹為例）

 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);
  }
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用