跳转至

# 树上随机游走

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

## 需要用到的定义

- 𝑇 =(𝑉,𝐸)T=(V,E): 所讨论的树
- 𝑑(𝑢)d(u): 结点 𝑢 u 的度数
- 𝑤(𝑢,𝑣)w(u,v): 结点 𝑢 u 与结点 𝑣 v 之间的边的边权
- 𝑝 𝑢 p u: 结点 𝑢 u 的父结点
- 𝑟 𝑜 𝑜 𝑡 root: 树的根结点
- 𝑠 𝑜 𝑛 𝑢 son u: 结点 𝑢 u 的子结点集合
- 𝑠 𝑖 𝑏 𝑙 𝑖 𝑛 𝑔 𝑢 sibling u: 结点 𝑢 u 的兄弟结点集合

## 向父结点走的期望距离

设 𝑓(𝑢)f(u) 代表 𝑢 u 结点走到其父结点 𝑝 𝑢 p u 的期望距离，则有：

𝑓(𝑢)=𝑤(𝑢,𝑝 𝑢)+∑𝑣∈𝑠 𝑜 𝑛 𝑢(𝑤(𝑢,𝑣)+𝑓(𝑣)+𝑓(𝑢))𝑑(𝑢)f(u)=w(u,p u)+∑v∈son u(w(u,v)+f(v)+f(u))d(u)

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

化简如下：

𝑓(𝑢)=𝑤(𝑢,𝑝 𝑢)+∑𝑣∈𝑠 𝑜 𝑛 𝑢(𝑤(𝑢,𝑣)+𝑓(𝑣)+𝑓(𝑢))𝑑(𝑢)=𝑤(𝑢,𝑝 𝑢)+∑𝑣∈𝑠 𝑜 𝑛 𝑢(𝑤(𝑢,𝑣)+𝑓(𝑣))+(𝑑(𝑢)−1)𝑓(𝑢)𝑑(𝑢)=𝑤(𝑢,𝑝 𝑢)+∑𝑣∈𝑠 𝑜 𝑛 𝑢(𝑤(𝑢,𝑣)+𝑓(𝑣))=∑(𝑢,𝑡)∈𝐸 𝑤(𝑢,𝑡)+∑𝑣∈𝑠 𝑜 𝑛 𝑢 𝑓(𝑣)f(u)=w(u,p u)+∑v∈son u(w(u,v)+f(v)+f(u))d(u)=w(u,p u)+∑v∈son u(w(u,v)+f(v))+(d(u)−1)f(u)d(u)=w(u,p u)+∑v∈son u(w(u,v)+f(v))=∑(u,t)∈E w(u,t)+∑v∈son u f(v)

对于叶子结点 𝑙 l，初始状态为 𝑓(𝑙) =𝑤(𝑝 𝑙,𝑙)f(l)=w(p l,l)．

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

𝑓(𝑢)=𝑑(𝑢)+∑𝑣∈𝑠 𝑜 𝑛 𝑢 𝑓(𝑣)f(u)=d(u)+∑v∈son u f(v)

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

## 向子结点走的期望距离

设 𝑔(𝑢)g(u) 代表 𝑝 𝑢 p u 结点走到其子结点 𝑢 u 的期望距离，则有：

𝑔(𝑢)=𝑤(𝑝 𝑢,𝑢)+(𝑤(𝑝 𝑢,𝑝 𝑝 𝑢)+𝑔(𝑝 𝑢)+𝑔(𝑢))+∑𝑠∈𝑠 𝑖 𝑏 𝑙 𝑖 𝑛 𝑔 𝑢(𝑤(𝑝 𝑢,𝑠)+𝑓(𝑠)+𝑔(𝑢))𝑑(𝑝 𝑢)g(u)=w(p u,u)+(w(p u,p p u)+g(p u)+g(u))+∑s∈sibling u(w(p u,s)+f(s)+g(u))d(p u)

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

化简如下：

𝑔(𝑢)=𝑤(𝑝 𝑢,𝑢)+(𝑤(𝑝 𝑢,𝑝 𝑝 𝑢)+𝑔(𝑝 𝑢)+𝑔(𝑢))+∑𝑠∈𝑠 𝑖 𝑏 𝑙 𝑖 𝑛 𝑔 𝑢(𝑤(𝑝 𝑢,𝑠)+𝑓(𝑠)+𝑔(𝑢))𝑑(𝑝 𝑢)=𝑤(𝑝 𝑢,𝑢)+𝑤(𝑝 𝑢,𝑝 𝑝 𝑢)+𝑔(𝑝 𝑢)+∑𝑠∈𝑠 𝑖 𝑏 𝑙 𝑖 𝑛 𝑔 𝑢(𝑤(𝑝 𝑢,𝑠)+𝑓(𝑠))+(𝑑(𝑝 𝑢)−1)𝑔(𝑢)𝑑(𝑝 𝑢)=𝑤(𝑝 𝑢,𝑢)+𝑤(𝑝 𝑢,𝑝 𝑝 𝑢)+𝑔(𝑝 𝑢)+∑𝑠∈𝑠 𝑖 𝑏 𝑙 𝑖 𝑛 𝑔 𝑢(𝑤(𝑝 𝑢,𝑠)+𝑓(𝑠))=∑(𝑝 𝑢,𝑡)∈𝐸 𝑤(𝑝 𝑢,𝑡)+𝑔(𝑝 𝑢)+∑𝑠∈𝑠 𝑖 𝑏 𝑙 𝑖 𝑛 𝑔 𝑢 𝑓(𝑠)=∑(𝑝 𝑢,𝑡)∈𝐸 𝑤(𝑝 𝑢,𝑡)+𝑔(𝑝 𝑢)+⎛⎜ ⎜⎝𝑓(𝑝 𝑢)−∑(𝑝 𝑢,𝑡)∈𝐸 𝑤(𝑝 𝑢,𝑡)−𝑓(𝑢)⎞⎟ ⎟⎠=𝑔(𝑝 𝑢)+𝑓(𝑝 𝑢)−𝑓(𝑢)g(u)=w(p u,u)+(w(p u,p p u)+g(p u)+g(u))+∑s∈sibling u(w(p u,s)+f(s)+g(u))d(p u)=w(p u,u)+w(p u,p p u)+g(p u)+∑s∈sibling u(w(p u,s)+f(s))+(d(p u)−1)g(u)d(p u)=w(p u,u)+w(p u,p p u)+g(p u)+∑s∈sibling u(w(p u,s)+f(s))=∑(p u,t)∈E w(p u,t)+g(p u)+∑s∈sibling u f(s)=∑(p u,t)∈E w(p u,t)+g(p u)+(f(p u)−∑(p u,t)∈E w(p u,t)−f(u))=g(p u)+f(p u)−f(u)

初始状态为 𝑔(r o o t) =0 g(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);
      }
    }

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, StableAgOH, aofall, CJTracer, CoelacanthusHex, Marcythm, Persdre, shuzhouliu
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用