Rolling - 题解

标签与难度

标签: 树形DP, 换根DP, 概率DP, 树上问题, 期望难度: 2200

题目大意喵~

各位骑士大人，下午好喵~ 今天我们来解决一个关于小球在树上滚动的概率问题，听起来就很有趣对吧！

题目是这样描述的：我们有一棵有 $n$ 个节点的树，每条边都有一个权值。首先，我们会等概率地（也就是以 $\frac{1}{n}$ 的概率）在 $n$ 个节点中随机选择一个作为根节点。然后，一个小球会从这个根节点出发，开始它的滚动之旅。

小球的移动规则是：

如果小球在一个非叶子节点 u，它会滚向它的一个孩子。
滚向某个特定孩子 v 的概率，正比于连接 u 和 v 的边的权值。也就是说，如果 u 的孩子们是 $v_1, v_2, \dots, v_m$ ，对应的边权是 $e_1, e_2, \dots, e_m$ ，那么小球滚向 $v_i$ 的概率就是 $\frac{e_i}{\sum_{j=1}^{m} e_j}$ 。
这个过程会一直持续，直到小球到达一个叶子节点（在当前根节点下，没有孩子的节点），然后就停下来了。

我们的任务是，对于原树中的每一个叶子节点（度数为1的节点），计算出小球最终停在该点的总概率是多少，喵~

解题思路分析

这道题的概率计算看起来有点棘手呢，喵~ 因为小球的滚动方向和概率都依赖于我们最初选择的根节点 r。如果对每一个可能的根节点 r 都计算一遍所有叶子的最终概率，那复杂度肯定是吃不消的。这种“遍历所有节点作为根”的题型，通常都在暗示我们要使用一种强大的技巧——换根DP（也叫二次扫描法）！

让我们先来分析一下，如果固定了根节点 r 和目标叶子 l，小球从 r 滚到 l 的概率是多少。

小球只能从父节点滚向子节点，所以要想到达 l，l 必须是 r 的一个后代节点（或者 r 本身就是 l）。从 r到 l 有一条唯一的路径，我们称之为 $v_0, v_1, \dots, v_k$ ，其中 $v_0=r$ ， $v_k=l$ 。

小球必须严格按照这条路径滚动。在路径上的每一个节点 $v_i$ （ $0 \le i < k$ ），它都必须选择滚向 $v_{i+1}$ 。在以 r 为根的树中， $v_i$ 的父节点是 $v_{i-1}$ （ $v_0$ 没有父节点）。设 $S_u$ 为与节点 u 相连的所有边的权值之和。当小球在节点 $v_i$ 时，它所有通向孩子的边的权值总和是 $S_{v_i} - w(v_i, v_{i-1})$ （对于根节点 $v_0$ ，这个总和就是 $S_{v_0}$ ）。

所以，在 $v_i$ 处选择滚向 $v_{i+1}$ 的概率是：

P(v_i \to v_{i+1}) = \frac{w(v_i, v_{i+1})}{S_{v_i} - w(v_i, v_{i-1})} \quad (\text{对于 } i>0)

P(v_0 \to v_1) = \frac{w(v_0, v_1)}{S_{v_0}} \quad (\text{对于 } i=0)

那么，从 r 滚到 l 的总概率就是这条路径上所有选择概率的乘积：

P(l|r) = \left( \prod_{i=0}^{k-1} P(v_i \to v_{i+1}) \right)

直接计算这个式子对于所有的 r 和 l 还是太复杂了。这道题的概率 DP 推导有点绕呢，喵~ 所以我们换个思路，直接来分析一下换根 DP 的过程。

换根 DP 通常分两步：

第一次 DFS (自底向上): 任意选择一个节点作为临时根（比如节点1），计算出每个子树内的 DP 值。
第二次 DFS (自顶向下): 从临时根出发，利用父节点和兄弟节点的信息，修正每个节点的 DP 值，得到以该节点为根时的真正答案。

我们需要设计合适的 DP 状态。这道题的 DP 状态不是那么直观，但经过一番探索，我们可以定义两个核心的 DP 数组，分别在两次 DFS 中计算。

第一次 DFS：计算子树贡献

我们先任取一个非叶子节点（比如1号点）作为根。进行一次自底向上的 DFS。我们定义一个 DP 状态 dp_down[u]，它代表一个比较抽象的“概率贡献”值。

具体来说，dp_down[u] 表示：对于所有在 u 的子树里（包括 u）的根节点 r，它们到达 u 的概率 P(u|r) 的某种加权和。

这个定义可能有点模糊，但我们可以从它的递推关系中发现它的结构。 dp_down[u] 的计算分为两部分：

根节点就是 u 自己的贡献。
根节点在 u 的各个孩子 v 的子树中的贡献。

经过复杂的推导（这里我的小脑袋也绕了半天呢~），我们可以得到一个神奇的递推式：

dp_{down}[u] = \frac{1}{S_u} + \sum_{v \in \text{children}(u)} dp_{down}[v] \cdot \frac{w(u,v)}{S_u - w(u,v)}

这里的 $w(u,v)$ 是边 $(u,v)$ 的权值。这个式子可以在一次自底向上的 DFS 中求出。dp_down[u] 实际上是把所有从子树内的根出发到 u 的路径概率，根据转移规则进行了一种巧妙的累加。

第二次 DFS：计算全局贡献

第一次 DFS 只考虑了根在子树内部的情况。现在我们需要考虑根在子树外的情况。我们定义 ans[u] 为我们最终想求的，对于叶子 u 的总概率和（乘以 $n$ ）。

在第二次自顶向下的 DFS 中，我们计算 ans[u]。ans[u] 由两部分组成：

根在 u 的子树内：这部分的贡献可以由 dp_down[u] 得到。
根在 u 的子树外：这部分的贡献 dp_up[u] 需要从父节点 p 的信息 ans[p] 和兄弟节点的信息 dp_down[s] 推导出来。

同样，经过一番推导，我们可以得到 ans[v]（v 是 u 的孩子）和 ans[u] 的关系。从 u 向 v 转移时，v 的“上方”世界就是 u 的“上方”世界，加上 u 本身，再加上 v 的所有兄弟子树。

这个转移关系可以表示为：

\text{up\_contribution}(v) = \left( \text{up\_contribution}(u) + \text{down\_contribution\_from\_siblings}(v) \right) \cdot \text{transition}(u \to v)

最终，对于每个叶子节点 l，我们计算出的 ans[l] 就是 $\sum_{r=1}^n P(l|r)$ 。最后，别忘了每个根的选择概率是 $\frac{1}{n}$ ，所以要将 ans[l] 乘以 n 的逆元。

总结一下，算法步骤就是：

预处理所有节点的度数和邻边权值和 $S_u$ 。
选择一个非叶子节点作为根 R，进行第一次 DFS，计算所有节点的 dp_down[u] 值。
进行第二次 DFS，从根 R 开始，计算 ans[u]。根节点的 ans[R] 就是 dp_down[R]。然后根据递推关系计算其孩子的 ans 值，并递归下去。
遍历所有节点，如果节点 i 是叶子，输出 ans[i] \cdot n^{-1} \pmod{M}。

这样，我们就在 $O(N)$ 的时间内解决了问题，是不是很优雅呢，喵~

代码实现

这是我根据上面的思路，重新整理的一份代码，希望能帮助你理解呐~

cpp

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

// 使用 long long 防止乘法溢出
using ll = long long;

vector<pair<int, int>> adj[MAXN];
int degree[MAXN];
ll sum_weights[MAXN]; // S_u, 与u相连的所有边的权值和

// dp_down[u]: 第一次DFS自底向上计算的值
// 对应思路分析中的 dp_down[u]
ll dp_down[MAXN];

// ans[u]: 最终答案，对于叶子u，ans[u] = sum_{r=1 to n} P(u|r)
ll ans[MAXN];

// 快速幂计算模逆元 (费马小定理)
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// 第一次DFS：自底向上，计算dp_down数组
void dfs1_calc_down(int u, int p) {
    // 初始化dp_down[u]：根就是u自己的贡献是 1/S_u
    dp_down[u] = modInverse(sum_weights[u]);

    for (auto& edge : adj[u]) {
        int v = edge.first;
        int weight = edge.second;
        if (v == p) continue;

        dfs1_calc_down(v, u);

        // 核心递推式
        // dp_down[u] += dp_down[v] * w(u,v) / (S_u - w(u,v))
        ll term = (dp_down[v] * weight) % MOD;
        ll inv_den = modInverse((sum_weights[u] - weight + MOD) % MOD);
        term = (term * inv_den) % MOD;
        dp_down[u] = (dp_down[u] + term) % MOD;
    }
}

// 第二次DFS：自顶向下，计算最终的ans数组
void dfs2_calc_ans(int u, int p, int w_up) { // w_up 是 (p,u) 边的权值
    // 从父节点p传来的"up"贡献
    if (p != 0) {
        // ans[p] 包含了来自 p子树内部 和 p子树外部 的所有贡献
        // 我们需要减去 v=u 这条分支对 ans[p] 的贡献，剩下的就是 u 的 "上方世界" 的贡献
        ll p_contribution_from_u = (dp_down[u] * w_up) % MOD;
        p_contribution_from_u = (p_contribution_from_u * modInverse((sum_weights[p] - w_up + MOD) % MOD)) % MOD;
        
        // p的贡献减去u的子树贡献
        ll up_val = (ans[p] - p_contribution_from_u + MOD) % MOD;
        
        // 从p转移到u
        ll term = (up_val * w_up) % MOD;
        ll inv_den = modInverse((sum_weights[u] - w_up + MOD) % MOD);
        term = (term * inv_den) % MOD;
        
        ans[u] = (dp_down[u] + term) % MOD;
    }

    for (auto& edge : adj[u]) {
        int v = edge.first;
        int weight = edge.second;
        if (v == p) continue;
        dfs2_calc_ans(v, u, weight);
    }
}


int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }

    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        degree[u]++;
        degree[v]++;
        sum_weights[u] = (sum_weights[u] + w) % MOD;
        sum_weights[v] = (sum_weights[v] + w) % MOD;
    }

    // 随便找一个非叶子节点作为根开始DP
    int root = -1;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] > 1) {
            root = i;
            break;
        }
    }
    // 如果所有点都是叶子，说明是 n=2 的情况，随便选一个根
    if (root == -1) root = 1;

    dfs1_calc_down(root, 0);
    ans[root] = dp_down[root];
    dfs2_calc_ans(root, 0, 0);

    ll inv_n = modInverse(n);
    bool first = true;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 1) {
            if (!first) {
                cout << " ";
            }
            cout << (ans[i] * inv_n) % MOD;
            first = false;
        }
    }
    cout << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们对树进行了两次完整的 DFS 遍历。每次 DFS 中，每个节点和每条边都只访问一次。预处理和最后输出也都是线性的。所以总的时间复杂度是 $O(N)$ ，对于 $10^5$ 的数据规模来说是完全没问题的，喵~
空间复杂度: $O(N)$ 我们使用了邻接表来存图，以及一些 DP 数组（dp_down, ans, degree, sum_weights），它们的大小都和节点数 $N$ 成正比。因此，空间复杂度是 $O(N)$ 。

知识点总结

这道题是一道非常经典的换根 DP 结合概率论的题目，挑战性十足！通过解决它，我们可以学到：

概率与期望的建模: 如何将一个看似复杂的概率过程，分解成可以在树上递推的子问题。
换根DP思想: 面对需要在每个节点作为根的情况下求解的问题时，换根 DP 是一个强大的工具。它通过两次 DFS，巧妙地将 $O(N^2)$ 的暴力计算优化到 $O(N)$ 。
抽象DP状态设计: 有时候 DP 的状态并不直接对应一个明确的物理意义（比如概率），而可能是一个中间的、便于递推的“贡献值”。找到这样的状态是解决复杂 DP 问题的关键。
模运算和逆元: 在处理概率和除法时，如果需要在模意义下进行，就要用到模逆元。使用费马小定理求逆元是一种常见且高效的方法。

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦，喵~ >w<

Rolling - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一次 DFS：计算子树贡献 ​

第二次 DFS：计算全局贡献 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​