树上随机游走问题

树概率 DP

字数统计: 843阅读时长: 4 min

 2022/08/31 

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

需要用到的定义

\(T=(V,E)\): 所讨论的树
\(d(u)\): \(u\) 结点的度数
\(w(u,v)\): \(u\) 结点与 \(v\) 结点之间的边的边权
\(p_u\): \(u\) 结点的父结点
\({son}_u\): \(u\) 结点的子结点集合
\({sibling}_u\): \(u\) 结点的兄弟结点集合

向父结点走的期望距离

设 \(f(u)\) 代表 \(u\) 结点走到其父结点 \(p_u\) 的期望距离，则有：

\[f(u) = \cfrac{w(u,p_u) + \sum\limits_{v \in {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 {son}_u}(w(u,v) + f(v) + f(u))}{d(u)} \\ &= \cfrac{w(u,p_u) + \sum\limits_{v \in {son}_u}(w(u,v) + f(v)) + (d(u)-1)f(u)}{d(u)} \\ &= w(u,p_u) + \sum\limits_{v \in {son}_u}(w(u,v) + f(v)) \\ &= \sum\limits_{(u,t) \in E}w(u,t) + \sum\limits_{v \in {son}_u}f(v) \end{aligned} \]

初始状态为 \(f(leaf) = 1\)。

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

\[f(u) = d(u) + \sum\limits_{v \in {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 {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 {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 {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 {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 {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(root) = 0\)。

代码实现（以无权树为例）

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

原文作者：AgOH

原文链接：https://stagoh.com/2022/08/31/random-walk-on-tree/

发表日期：August 31st 2022, 4:37:43 pm

更新日期：December 17th 2023, 5:08:54 pm

Next Post

使用位运算枚举二进制子集的巧妙方法
Previous Post

每日刷题打卡

CATALOG

1. 需要用到的定义
2. 向父结点走的期望距离
3. 向子结点走的期望距离
4. 代码实现（以无权树为例）