什么是樹上隨機(jī)游走？我們可以假設(shè)給定一棵樹，樹的某個結(jié)點上有一個硬幣，在某一時刻硬幣會等概率地移動到鄰接結(jié)點上，問硬幣移動到鄰接結(jié)點上的期望距離。

1. 樹上隨機(jī)游走用到的定義：

●  所討論的樹

● 結(jié)點的度數(shù)

● 結(jié)點與 v 結(jié)點之間的邊的邊權(quán)

● 結(jié)點的父結(jié)點

● 結(jié)點的子結(jié)點集合

● 結(jié)點的兄弟結(jié)點集合

2. 向父結(jié)點走的期望距離

設(shè)代表 u 結(jié)點走到其父結(jié)點的期望距離，則有：

分子中的前半部分代表直接走向了父結(jié)點，后半部分代表先走向了子結(jié)點再由子結(jié)點走回來然后再向父結(jié)點走；分母代表從 u 結(jié)點走向其任何鄰接點的概率相同。

化簡如下：

初始狀態(tài)為。

當(dāng)樹上所有邊的邊權(quán)都為 1 時，上式可化為：

即 u 子樹的所有結(jié)點的度數(shù)和，也即 u 子樹大小的兩倍-1（每個結(jié)點連向其父親的邊都有且只有一條，除 u 與之間的邊只有 1 點度數(shù)的貢獻(xiàn)外，每條邊會產(chǎn)生 2 點度數(shù)的貢獻(xiàn)）。

3. 向子結(jié)點走的期望距離

設(shè)  代表結(jié)點走到其子結(jié)點 u 的期望距離，則有：

分子中的第一部分代表直接走向了子結(jié)點 u，第二部分代表先走向了父結(jié)點再由父結(jié)點走回來然后再向 u 結(jié)點走，第三部分代表先走向 u 結(jié)點的兄弟結(jié)點再由其走回來然后再向 u 結(jié)點走；分母代表從結(jié)點走向其任何鄰接點的概率相同。

化簡如下：

初始狀態(tài)為。

代碼實現(xiàn)（以無權(quán)樹為例）

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